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 :)
A sprawdzanie literka po literce, a potem a potem coś ala średnia ważona?
typu:
(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:
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.