Trouvez la distance d'édition (distance de Levenshtein) avec python

Concernant la distance de montage, c'est un peu vieux, mais l'article de Naoya Ito est utile. En termes simples, il s'agit d'une méthode permettant d'exprimer la proximité de deux chaînes de caractères sous forme de valeur numérique.

Référence: Editing Distance (Levenshtein Distance) - Naoya's Hatena Diary

Préparation

Il y avait un paquet appelé python-Levenshtein, alors mettons-le.

$ sudo pip install python-Levenshtein

Essayer

Écrivons un code comme celui-ci.

#!/usr/bin/env python
# coding: utf8

import Levenshtein

string1 = "Taiji Inoue"
string2 = "Yasuji Inoue"

string1 = string1.decode('utf-8')
string2 = string2.decode('utf-8')

print Levenshtein.distance(string1, string2)
$ python levenshtein.py
1

Le japonais est également OK. Si vous remplacez un caractère, ce sera le caractère correct, donc la distance d'édition sera de 1.

Je ne suis pas doué pour taper le mot python, et quand je le remarque, il devient pyhton. La distance d'édition entre pyhton et python est de 2. (Parce que ce sera pareil si vous échangez les deux lettres)

prime

En regardant la Documentation, il semble que vous puissiez également calculer la distance Jaro-Winkler et ainsi de suite.

Bonus 2

Si vous l'enregistrez en tant que MySQL stocké comme celui ci-dessous, il ressemblera à ORDER BY LEVENSHTEIN (titre, "Hogehoge"). C'est pratique car il sera affiché dans l'ordre des lettres. Cependant, l'index ne fonctionne pas, donc si vous recherchez tous les enregistrements et que le nombre d'enregistrements est important, la requête sera assez lourde.

https://github.com/fza/mysql-doctrine-levenshtein-function

Relation

PHP- [Prise en charge multi-octets] Recherche de la distance de Levenstein-Qiita

Recommended Posts

Trouvez la distance d'édition (distance de Levenshtein) avec python
Ecrire un programme python pour trouver la distance d'édition [python] [distance Levenshtein]
Trouvez le maximum de Python
Trouvez la valeur de l'humeur avec python (Rike Koi)
Trouvez l'itinéraire le plus court avec l'algorithme de Python Dijkstra
Trouver des erreurs en Python
Appelez l'API avec python3.
Trouvez la valeur maximale python (amélioré)
J'ai essayé de trouver l'entropie de l'image avec python
[Python] Trouvez la deuxième plus petite valeur.
Obtenez la météo avec les requêtes Python
Obtenez la météo avec les requêtes Python 2
Accédez à l'API Etherpad-lite avec Python
Installer le plug-in Python avec Netbeans 8.0.2
J'ai aimé le tweet avec python. ..
J'ai essayé de calculer la "distance de Lebenstein" en utilisant Python
Maîtriser le type avec Python [compatible Python 3.9]
Trouver la similitude d'image avec Python + OpenCV
Découvrez le changement mystérieux de la description du livre illustré Pokemon par Levenstein Distance
Rendre la console Python couverte d'UNKO
Trouvons la valeur maximale python (correction ver)
Derrière le flyer: utiliser Docker avec Python
Vérifier l'existence du fichier avec python
Trouvez la valeur SHA256 avec R (avec bonus)
[Python] Récupère le nom de la variable avec str
Rechercher le labyrinthe avec l'algorithme python A *
Lisons le fichier RINEX avec Python ①
Travailler avec OpenStack à l'aide du SDK Python
Télécharger des fichiers sur le Web avec Python
Apprenez le modèle de conception "Singleton" avec Python
[Python] Utiliser automatiquement le navigateur avec Selenium
Apprenez le modèle de conception "Façade" avec Python
La route de la compilation vers Python 3 avec Thrift
FizzBuzz en Python3
Grattage avec Python
Statistiques avec python
Grattage avec Python
Twilio avec Python
Intégrer avec Python
Jouez avec 2016-Python
AES256 avec python
Testé avec Python
python commence par ()
avec syntaxe (Python)
Retrouvez les termes généraux de la séquence de Tribonacci en algèbre linéaire et Python
Bingo avec python
Zundokokiyoshi avec python
Excel avec Python
Micro-ordinateur avec Python
Cast avec python
J'ai essayé de "lisser" l'image avec Python + OpenCV
[Python] Récupérez les fichiers dans le dossier avec Python
Préparer l'environnement d'exécution de Python3 avec Docker
Trouvez le différentiel du second ordre avec la différenciation automatique JAX
Mathématiques Todai 2016 résolues avec Python
J'ai essayé de "différencier" l'image avec Python + OpenCV
[Note] Exportez le html du site avec python.
Trouvez la position au-dessus du seuil avec NumPy
Le moyen le plus simple de synthétiser la voix avec python
Essayez de résoudre le diagramme homme-machine avec Python