Distance ultramétrique

La distance est dite ultramétrique si de plus :

Nom	Propriété
Ultramétrie	${\displaystyle \forall a,b,c\in E:d(a,c)\leq \max(d(a,b),d(b,c)).}$

Un exemple de telle distance intervient de façon cruciale dans la théorie des valuations p-adiques. L'interprétation géométrique de l'inégalité triangulaire dans un espace ultramétrique amène à dire que tous les triangles sont isocèles ; de plus, toutes les boules de rayon donné définies sur cet ensemble constituent une partition de cet ensemble ; en faisant croître ce rayon depuis 0, l'espace se trouve doté d'une structure hiérarchique de proximité, utilisable en classification automatique, en particulier pour le clustering hiérarchique.

Distance sur des espaces vectoriels

Distance de Manhattan (chemins rouge, jaune et bleu) contre distance euclidienne en vert.

Visualisation de quelques distances et semi-distances : distances des points du plan par rapport au point origine et à un autre point de référence^[4]

Sur un espace vectoriel normé ${\displaystyle (E,\|\cdot \|)}$, la distance d « induite par » la norme^[5] ${\displaystyle \|\cdot \|}$ est définie par :

${\displaystyle \forall (x,y)\in E\times E\quad d(x,y)=\|y-x\|}$.

En particulier, dans ℝⁿ (donc aussi dans ses sous-ensembles^[6]), on peut définir de plusieurs manières la distance entre deux points, bien qu'elle soit généralement donnée par la distance euclidienne (ou 2-distance). Soit deux points de E, (x₁, x₂, …,x_n) et (y₁, y₂, …,y_n), on exprime les différentes distances ainsi :

Nom	Paramètre	Fonction
distance de Manhattan	1-distance	${\displaystyle \sum _{i=1}^{n}|x_{i}-y_{i}|}$
distance euclidienne	2-distance	${\displaystyle {\sqrt {\sum _{i=1}^{n}(x_{i}-y_{i})^{2}}}}$
distance de Minkowski	p-distance	${\displaystyle {\sqrt[{p}]{\sum _{i=1}^{n}|x_{i}-y_{i}|^{p}}}}$
distance de Tchebychev	∞-distance	${\displaystyle \lim _{p\to \infty }{\sqrt[{p}]{\sum _{i=1}^{n}|x_{i}-y_{i}|^{p}}}=\sup _{1\leq i\leq n}{|x_{i}-y_{i}|}}$

La 2-distance permet de généraliser l'application du théorème de Pythagore à un espace de dimension n. C'est la distance la plus « intuitive ».

La p-distance est rarement utilisée en dehors des cas p = 1, 2 ou ∞. L'∞-distance présente la particularité amusante de permettre la définition en toute rigueur de sphères cubiques (voir oxymore). La 1-distance permet de définir des sphères octaédriques.

Distance discrète

Sur n'importe quel ensemble, la distance discrète d est définie par : si x = y alors d(x, y) = 0 et sinon, d(x, y) = 1.

Distance sur une sphère

Distances entre deux permutations

Il est également possible de définir des distances entre des permutations. L'exemple suivant est très utilisé dans le réarrangement de génomes. Soit S un ensemble de permutations modélisant diverses opérations ; alors la distance entre deux permutations π et σ est la longueur d'une séquence minimale formée du produit d'éléments de S telle que cette séquence transforme π en σ.

On peut utiliser la distance de Kendall qui mesure le nombre de transpositions permettant de passer d'une permutation à une autre, ce qui revient à calculer l'indice tau = (somme des couples concordants) - (somme des couples discordants) / n(n-1)/2. L'indice varie de -1 à +1 selon la ressemblance entre les permutations.

Ces distances peuvent également servir à mesurer, de diverses manières, le désordre présent dans une séquence. On utilise alors ces mesures pour analyser les performances de divers algorithmes de tri, ou pour construire de nouveaux algorithmes de tri qui effectuent un nombre de comparaisons optimal par rapport à la mesure de désordre choisie.

Distance de Levenshtein

La distance de Levenshtein est un exemple de distance définie sur l'ensemble des chaînes de caractères. Elle est définie pour deux chaînes A et B comme le nombre minimal d'opération d'ajout/suppression/remplacement de caractères pour transformer la chaîne A en la chaîne B.

Exemples:

• Levenshtein('BONJOUR', 'BONSOIR')=2 (il est nécessaire et suffisant de remplacer 'J' par 'S' et 'U' par 'I').
• Levenshtein('DEBUT', 'FIN')=5
• Levenshtein('DUNKERQUE', 'PERPIGNAN')=9^[7].

Ce type de distance est couramment utilisé pour des applications de filtrage/correction d'erreurs, par exemple la correction automatique pour des programmes de traitement de texte (le programme va rechercher dans un dictionnaire les mots présentant les distances les plus faibles avec le mot mal orthographié), l'appareillement de lectures optiques de plaques minéralogiques...

Il existe des variantes de cette distance, telles que la distance de Damerau-Levenshtein.

Le même principe général peut être utilisé pour les applications de reconnaissance de formes.

Distance entre deux ensembles

Soient E₁ et E₂ deux parties non vides d'un espace métrique E muni d'une distance d, on définit la distance entre ces deux ensembles comme : ${\displaystyle d(E_{1},E_{2})=\inf\{d(x,y)\mid (x,y)\in E_{1}\times E_{2}\}.}$

C'est un réel positif, comme borne inférieure d'un ensemble non vide de réels positifs.

N.B.

Cette « distance » n'est pas une distance sur l'ensemble des parties de E au sens des axiomes définis plus haut. En particulier si la distance entre deux ensembles est nulle, on ne peut pas en déduire que ces ensembles sont égaux, ni même que leurs adhérences se rencontrent.

Néanmoins, il est possible de définir une vraie distance entre les parties compactes d'un espace métrique. Pour cela, voir : distance de Hausdorff.

Théorème

Avec les notations ci-dessus, ${\displaystyle d(E_{1},E_{2})=d({\bar {E_{1}}},{\bar {E_{2}}})}$, où ${\displaystyle {\bar {F}}}$ désigne l'adhérence d'une partie ${\displaystyle F}$ de ${\displaystyle E}$^[8].

Distance d'un point à une partie

On peut particulariser la définition précédente en prenant l'un des deux ensembles réduit à un point.

Si A est une partie non vide d'un espace métrique E, et si x est élément de E, on définit la distance de x à A comme une borne inférieure :

${\displaystyle d(x,A)=\inf\{d(x,a)\mid a\in A\}.}$

C'est^[9] le rayon de la plus grande boule ouverte de centre x qui ne rencontre pas A.

On prendra garde au fait que d(x, A) = 0 n'implique pas en général que x soit élément de A. Par exemple, dans ℝ muni de la valeur absolue, la distance de 0 à l'intervalle ouvert ]0, 1[ est nulle, ou la distance de tout réel à l'ensemble des rationnels est nulle également.

Plus précisément, la distance de x à A est nulle si et seulement si^[10],[11] x est un point adhérent à A (autrement dit : l'implication précédente est vraie si et seulement si A est fermé). Plus généralement, la distance de x à A est égale à la distance de x à l'adhérence de A.

L'application de E dans ℝ qui à tout élément x de E associe d(x, A) est continue, et même 1-lipschitzienne^[12],[13] : ${\displaystyle \forall x,y\in E\quad |d(x,A)-d(y,A)|\leq d(x,y)}$.

Distance algébrique

Soit deux points A et B d'un espace affine par lesquels passe une droite orientée (une droite munie d'un sens, c'est-à-dire engendrée par un vecteur ${\displaystyle {\vec {v}}}$ non nul). On appelle distance algébrique de A vers B le réel tel que :

• sa valeur absolue soit la distance (définie ci-dessus) entre A et B
• si la valeur est non nulle :
  • le réel soit positif dans le cas où le vecteur ${\displaystyle {\overrightarrow {\rm {AB}}}}$ est de même sens que ${\displaystyle {\vec {v}}}$, c'est-à-dire égal à ${\displaystyle k{\vec {v}}}$, avec ${\displaystyle k>0}$,
  • négatif sinon.

On peut démontrer que la distance algébrique de A vers B (notée ${\displaystyle d_{a}(\mathrm {A} ,\mathrm {B} )}$) vaut :

${\displaystyle d_{a}(\mathrm {A} ,\mathrm {B} )={\frac {{\overrightarrow {\mathrm {AB} }}.{\vec {v}}}{\|{\vec {v}}\|}}}$

Attention, la distance algébrique n'est pas une distance, puisqu'elle est non symétrique :

${\displaystyle d_{a}(\mathrm {A} ,\mathrm {B} )=-d_{a}(\mathrm {B} ,\mathrm {A} )}$