Hoe vergelijkbaar zijn twee woorden

is there more accurate algorithm than "Levenshtein distance" algorithm?? http://en.wikipedia.org/wiki/Levenshtein_distance

0
@DanielFischer Levenshtein retourneert slechte resultaten met korte woorden. Ik zoek bijvoorbeeld naar een bestand voor vergelijkbare woorden naar een bepaald woord
, ik controleerde het algoritme voor elk woord in het bestand, als het int retourneert, is dat minder dan 3 het is vergelijkbaar, het werkt voor grote woorden maar met kleine woorden zal het niet wanneer ik zoek naar het woord "één" soortgelijke woorden zijn "kern, regel, open, bewegen, lang, code"
toegevoegd de auteur Evan Lévesque, de bron
@Regexident Ik heb dat geprobeerd maar het geeft niet de vereiste nauwkeurigheid met te korte woorden, maar met andere woorden, het werkt heel goed, bijvoorbeeld als ik naar soortgelijke woorden op zoek was naar het woord "programma" geeft het "programma" terug en dat is perfect maar niet met te kleine woorden
toegevoegd de auteur Evan Lévesque, de bron
@Regexident Ik denk dat je gelijk hebt, het is gebrek aan precisie bij het meten van de gelijkenis van korte woorden, ik heb altijd een statische precisie gebruikt, het moet dynamisch zijn Bedankt
toegevoegd de auteur Evan Lévesque, de bron
Het hangt af van hoe u nauwkeurigheid definieert.
toegevoegd de auteur Jonathan M, de bron
Welke notie van gelijkenis zoek je? Zonder te weten wat je wilt, is het onmogelijk om andere maatregelen te suggereren.
toegevoegd de auteur Daniel Fischer, de bron
In termen van bewerkingsafstand lijken alle korte woorden nogal op elkaar, er is geen mogelijkheid omheen. Schalen volgens de lengte, zoals Regexident suggereerde, kan bevredigende resultaten opleveren, anders moet u een duidelijke specificatie vinden van de overeenkomst die u wenst.
toegevoegd de auteur Daniel Fischer, de bron
Waarom is Levenshtein niet geschikt voor u?
toegevoegd de auteur kol, de bron
@AymanJitan: u moet de bewerkingsafstand vergelijken met de lengten van beide woorden (min, max, avg, uw keuze). (mijn antwoord bijgewerkt)
toegevoegd de auteur Regexident, de bron
@AymanJitan: Nou, dat komt simpelweg door het gebrek aan precisie bij het meten van de gelijkenis van korte woorden, omdat een woord met lengte 4 slechts 5 mogelijke overeenkomsten met een ander gegeven woord kan hebben: 0%, 25%, 50%, 75%, 100%. Je kunt er niet veel aan doen. Het enige dat in mijn gedachten zou komen, zou zijn om een ​​soort van demping van de toegestane variantie te gebruiken met behulp van een logaritmische schaal.
toegevoegd de auteur Regexident, de bron

1 antwoord

Er is de afstand tussen Damerau en Levenshtein , die ondersteuning biedt voor karaktertransposities en meer dekking biedt voor veelvoorkomende typefouten.

Ga als volgt te werk om een ​​overeenkomstpercentage te krijgen voor Levenshtein of Damerau-Levenshtein :

int relative_similarity = 1.0 - 1.0/((len(x) + len(y))/2) * lev(x, y); //untested

Je kunt ook een kijkje nemen op de langste algemene subsequentie als een metriek van gelijkenis.

De volgende zijn er

die fonetische matching-algoritmen zijn.

Hoewel Smith en de Duitse tegenhanger Schmidt met de bewerkingsafstand (a.k.a Levenshtein) heel anders zouden zijn, zouden Soundex en MEtaphone ze fonetisch gelijkaardig of zelfs equivalent vinden.


Maar zonder dat u ons vertelt wat er fout is over de zuivere Levenshtein-afstand is het moeilijk een beter algoritme te raden.

4
toegevoegd
Damerau-Levenshtein afstand is meer accuraat dat de (klassieke) Levenshtein en Levenshtein slechte resultaten retourneren met soort woorden
toegevoegd de auteur Evan Lévesque, de bron
@AymanJitan: Damerau-Levenshtein is ook geen echte tekstmetriek (omdat deze niet voldoet aan de driehoeksongelijkheid), wat in het geval van BKTrees, b.v. kan een nogal slechte zaak zijn. Zonder dat u ons meer informatie geeft over wat er mis is met de gebruikelijke algoritmen, is het bijna onmogelijk om nuttige aanbevelingen te doen. "Gelijkaardig" kan zo ongeveer alles betekenen: woordlengte, woordvorm, fonetiek, semantische betekenis, ...
toegevoegd de auteur Regexident, de bron