Co to są niektóre algorytmy porównywania podobnych łańcuchów?

Question

Potrzebuję porównać ciągi znaków, aby zdecydować, czy reprezentują one to samo. Dotyczy to tytułów przypadków wprowadzanych przez ludzi, w których skróty i inne drobne szczegóły mogą się różnić. Na przykład, należy rozważyć następujące dwa tytuły:

std::string first = "Henry C. Harper v. The Law Offices of Huey & Luey, LLP"; 

W przeciwieństwie do:

std::string second = "Harper v. The Law Offices of Huey & Luey, LLP"; 

ludzka może szybko ocenić, że są to najprawdopodobniej jedno i to samo. Obecne podejście Brałem jest normalizacja struny przez lowercasing wszystkie litery i usunięcie wszystkich znaków interpunkcyjnych i dając obowiązuje:

std::string firstNormalized = "henrycharpervthelawofficesofhueylueyllp"; 

oraz:

std::string secondNormalized = "harpervthelawofficesofhueylueyllp"; 

Porównując w tym przypadku, jeden jest pod-sekwencja z drugiej strony, ale można sobie wyobrazić inne, bardziej skomplikowane odmiany, w których niekoniecznie występuje, ale mają wspólne pod-sekwencje znaczące. Mogą również występować przypadkowe błędy związane z wprowadzaniem danych, takie jak transponowane litery i błędy ortograficzne.

Być może jakiś program różnicowy może pomóc? Widziałem dobre programy różnicowe dla porównania różnic w kodzie do sprawdzenia, czy jest coś takiego na podstawie postaci, może w podbiciu? Gdybyś mógł policzyć liczbę kolejnych wspólnych bohaterów i przyjąć stosunek do postaci, które nie byłyby udostępnione, być może byłaby to dobra heurystyka?

Koniec końców, potrzebuję Boolowskiej decyzji, czy uznać je za takie samo czy nie. Nie musi być perfekcyjna, ale idealnie powinna być zła.

Jakiego algorytmu mogę użyć, aby uzyskać pewne dane liczbowe na temat tego, jak podobne są te dwa łańcuchy, które mogę następnie przekształcić w odpowiedź "tak/nie" za pomocą heurystyki?

Answer 1

Czego szukasz, to algorytmy o nazwie String Metric. Istnieje ich znaczna liczba, z których wiele ma podobne cechy. Wśród bardziej popularnych:

• Levenshtein Distance: Minimalna liczba edycji jednoznakowych wymaganych do zmiany jednego słowa na inny. Ciągi nie muszą mieć tej samej długości.
• Hamming Distance: Liczba znaków, które są różne w dwóch ciągach o jednakowej długości.
• Smith–Waterman: Rodzina algorytmów do obliczania podobieństw zmiennych zmiennych.
• Sørensen–Dice Coefficient: Algorytm podobieństwa, który oblicza współczynniki różnicowe sąsiednich par znaków.

Zobacz na ten temat także inne artykuły na temat wiki page.

Answer 2

Damerau Levenshtein distance to kolejny algorytm porównywania dwóch ciągów i jest podobny do algorytmu odległości Levenshteina. Różnica między nimi polega na tym, że może również sprawdzać transpozycje między znakami, a tym samym może dawać lepszy wynik dla korekcji błędów.

na przykład: odległość między Levenshteina night i nigth wynosi 2 ale Damerau Levenshteina odległość pomiędzy night i nigth będą 1, ponieważ jest to tylko wymiany pary znaków.

Answer 3

Możesz użyć do tego ngrams. Na przykład, przekształć dwa łańcuchy w słowo trygramy (zwykle małe litery) i porównaj ich procent, które są sobie równe.

Twoim wyzwaniem jest zdefiniowanie minimalnego procentu podobieństwa.

http://en.wikipedia.org/wiki/N-gram