Program do porównywania dwóch tekstów.

Witam, mam napisać program do porównywania dwóch tekstów i sprawdzać w ilu procentach są podobne. Ma to działać na zasadzie ,że są dwa zdania np:

Ala ma kota
Ala ma psa

I mam sprawdzić w ilu procentach zdania są do siebie podobne.
Myślę żeby pobierać teksty z plików i następnie je porównać lecz nie mam pojęcia jak by miało wyglądać to porównanie, wstępnie myślałem o jakiejś liście . Czy ktoś jest w stanie mi pomóc w tej sprawie?

A co z takim przypadkiem?

Ala ma kota
ma kota Ala

Możesz obliczać odległość Levenshteina poszczególnych słów i zapisywać różnice, ale przypadek czy porównujesz 2 słowo z drugim itp czy inne przypadki wchodza w gre.

Bo to co napisał @MarekR22
albo np:

Ala ma kota
Ala ma w kota

Ewentualnie skorzystaj z gotowej biblioteki
https://github.com/duckie/difflib
https://code.google.com/archive/p/google-diff-match-patch/

Ewentualnie poszperaj na githubie za kodem źródłowym svn lub git'a i podpatrz jak oni to robią :) oni wyłapują różniące się linie i co się w konkretnych liniach różni :)

http://www.geeksforgeeks.org/dynamic-programming-set-5-edit-distance/

A sprawdzanie literka po literce, a potem a potem coś ala średnia ważona?
typu:

1. Sprawdzamy czy string1.at(0) == string2.at(0)(i tak dalej i tak dalej) , jeżeli tak to: jakaś nasza zmienna: podobieństwo++;
2. Bierzemy

 (podobieństwo/ ( ceil(string1.size()+string2.size()) / 2)) *100;

Na razie chcę zrobić taki program jak napisałem, ale nie wiem jak wczytywać tekst do listy i w jaki sposób to porównać. Może ktoś by coś podpowiedział? ;)

razor17 napisał(a):

Na razie chcę zrobić taki program jak napisałem, ale nie wiem jak wczytywać tekst do listy i w jaki sposób to porównać. Może ktoś by coś podpowiedział? ;)

Czyli nic Nie Wiesz:) jak wczytac plik tekstowy: https://stackoverflow.com/questions/8365013/reading-line-from-text-file-and-putting-the-strings-into-a-vector
A algorytm Ci podalem, to standard w porownywaniu tekstow.

Ok dzięki Panowie za pomoc udało się ogarnąć. :)

Link od @lion137 to opisana kulawa implementacja odległości Levenshteina wspomnianej przez @daniel1302.
Radzę wygooglać Levenshteina a znajdziesz szybsze rozwiązanie, o mniejszej złożoności czasowej.

I mam sprawdzić w ilu procentach zdania są do siebie podobne.

Ciekawe jak przeliczysz odległość Levenshteina na procenty? Może w ten spposób:

auto maximumDistance = std::max(a.length(), b.length());
auto percentOfSimilarity = (maximumDistance - Levenshteinstd::max(a.length(), b.length())) * 100.0 / maximumDistance;

MarekR22 napisał(a):

Link od @lion137 to opisana kulawa implementacja odległości Levenshteina wspomnianej przez @daniel1302.
Radzę wygooglać Levenshteina a znajdziesz szybsze rozwiązanie, o mniejszej złożoności czasowej.

I mam sprawdzić w ilu procentach zdania są do siebie podobne.

Ciekawe jak przeliczysz odległość Levenshteina na procenty? Może w ten spposób:

Kopiuj

auto maximumDistance = std::max(a.length(), b.length());
auto percentOfSimilarity = (maximumDistance - Levenshteinstd::max(a.length(), b.length())) * 100.0 / maximumDistance;

Jaka kulawa? Dynamic programming na ogol jest szybkie, dla zabawy pisalem z tym auto complete I dalo sie uzywac.