Irmen's blog

Fuzzy (approximate) string compare

Met Fuzzy string compare bedoel ik het vergelijken van twee strings en dan een uitkomst krijgen die aangeeft hoe veel de strings op elkaar lijken. Dat wil zeggen, het is dus geen absolute string compare (die alleen maar aangeeft of 2 strings hetzelfde zijn of niet), maar een meer kwantitatieve string vergelijking.

Het kan gebruikt worden om bijvoorbeeld typefouten uit commando's te halen, een bepaalde vorm van spellingscontrole, of voor andere natuurlijke-taal toepassingen.

Voor Python zijn er een aantal modules beschikbaar die een fuzzy string compare functie bieden.

QUERTY- of proteïne afwijking

Daarnet heeft Rob Hooft op comp.lang.python een interessante module gepost die een algoritme hanteert dat normaal gebruikt wordt voor het vergelijken van proteïnes, maar dus nu op ASCII strings werkt. De uitslag is een float die negatief is als de strings heel erg verschillen en oploopt tot len(s)+1 als de strings precies hetzelfde zijn, de score is op te vatten als 'het aantal overenkomende letters'. Het algorithme gebruikt de layout van het QUERTY toetsenbord om afwijkingen tussen de strings te bepalen en is dus beperkt tot ASCII strings (en alleen zinvol als mensen gebruik maken van een QUERTY toetsenbord), maar daarom wel zeer geschikt om een ingevoerd commando te vergelijken met alle mogelijke commando's die mogelijk zijn en zo typfouten te herkennen. Waarom niet genormaliseerde score 0.0 tot 1.0? Rob: maakt niet uit als je alleen een 'best score' van een rijtje strings wilt hebben. De negatieve resultaten komen voor als de strings niet op elkaar lijken en ook nog eens niet dezelfde lengte hebben.

Hier te vinden: comparestrings.py.

Python standard library

In de standard lib hebben we difflib met de functie get_close_matches. Groot voordeel dat deze dus standaard bij Python zit.

Febrl (biometrisch)

Febrl bevat een aantal string compare functies, waaronder ook de edit distance of Levenshtein distance functie. Van die laatste is ook op Useless Python een implementatie te vinden.

Apse

Een extension module (geschreven in C): Apse. Benodigd: python, SWIG, C compiler.

Java

SecondString is een open-source pakket met Java implementaties van een heleboel string compare algorithmes. Dat moet niet al te moeilijk te porten zijn naar Python.