Signature

Une signature est un ensemble de données numériques, logiques ou symboliques constituant une suite dont chaque position est représentative d’une caractéristique d’un élément. Par exemple :

  • 01101110001010011 est une signature logique
  • 12.5.7.45.892.3.14 est une signature numérique
  • HLLLHLMMHMLMHH est une signature symbolique sur {L, M, H}
  • vert-12-A5-GT est une signature mixte

les signatures permettent de comparer deux éléments. Il est possible de définir des conventions de calcul d’une distance entre deux signatures. Par exemple :

  • la distance entre deux signatures logiques peut être égale au nombre de positions différentes : d(01101110001010011, 10010111101100010) = 10
  • la distance entre deux signatures symboliques nécessite de valoriser les symboles. Par exemple H=5, M=3 et L=1 d(HLLLHLMMHMLMHH, HLMMMHHMLLHLLH) = 28

Les signatures permettent aussi d’identifier des marqueurs significatifs. Ces marqueurs peuvent caractériser une famille de cas. Par exemple :

  • *****11**01**001* est un marqueur commun aux deux signatures logiques ci-dessus. Il peut constituer un masque permettant de trier les éléments.
  • HL*****M*****H est un marqueur présent dans les deux signatures symboliques ci-dessus. Il peut constituer une famille d’éléments.

Empreinte

Une empreinte est un ensemble de données numériques constituant une suite où chaque position caractérise la trace laissée par l’élément sur une référence.La trace se matérialise comme la différence entre la référence et l’élément pour chacune des positions. Par exemple :

  • si 01101110001010011 est la signature de la référence et 10010111101100010 celle de l’élément, l’empreinte de l’élément sur la référence sera 11111001100110001 ou chaque 1 représente une position impactée (les positions des signatures sont différentes) et chaque 0 une position non impactée (les positions des signatures sont égales).
  • si HLLLHLMMHMLMHH est la signature de référence et HLMMMHHMLLHLLH celle de l’élément, l’empreinte de l’élément sur la référence sera 00111210212120 ou chaque 1 représente une position impactée (les positions des signatures sont différentes, L et M ou M et H), chaque 2 représente une position impactée plus profondément (deux niveaux éloignes H et L) et chaque 0 une position non impactée (les positions des signatures sont égales).

On peut également définir une distance entre deux empreintes et des marqueurs caractéristiques de certaines familles d’empreintes.

Distance

Les distances entre les signatures et les distances entre les empreintes constituent des espaces non euclidiens.
d(A,C) ≠ d(A,B) + d(B,C)

en revanche on a :

|d(A,B) – d(B,C)| ≤ d(A,C) ≤ d(A,B) + d(B,C)