Porównywanie słów w dwóch zbiorach

0

Cześć,

jakie są dobre sposoby na porównywanie słów w dwóch artykułach / zbiorach?

Zastanawiam się w jaki sposób mając listę słów efektywnie je porównać z artykułem, który znajdę np. w portalu internetowym i zrobić na tym portalu jakieś przekształcenia lub wyszukania.
Zależałoby mi, żeby to było sprawne dla artykułów zawierających nawet do tych kilku tysięcy słów + porównania tych słów nawet z całym słownikiem całego języka. Tak, aby frontend mógł praktycznie płynnie działać z niewielkim opóźnieniem.

1

Lista słów jest stała?

2

Cos ala wykrywanie plagiatow? Karp-Rabin
https://en.m.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm

(I inne algorytmy tekstowe)

1

Ponieważ jest zainteresowanie to postaram się to krótko opisać.

Jest to słownik algorytmiczny. Mam w nim 76 tysięcy rdzeni. I mamy 255 grup odmian.
Każda grupa zwiera wykaz końcówek, które mogą się łączyć z danym rdzeniem.
Pokażę na przykładzie jednej grupy jak to działa.

2R M1b
0SZA_L 00R 1001000 0000000 0000000 0000000 0000000 0000000
1SZA_LA 00R 0100000 0000000 0000000 0000000 0000000 0000000
2SZA_LOWI 00R 0010000 0000000 0000000 0000000 0000000 0000000
3SZA_LEM 00R 0000100 0000000 0000000 0000000 0000000 0000000
4SZA_LU 00R 0000011 0000000 0000000 0000000 0000000 0000000
5SZA_LOWY 05P 1001001 0000000 0000000 0000000 0000000 0000000
6SZA_LOWA 05P 0000000 0000000 1000001 0000000 0000000 0000000
7SZA_LOWE 05P 0000000 1001001 0000000 1001001 1001001 1001001
8SZA_LOWEGO 05P 0101000 0000000 0000000 0000000 0100000 0000000
9SZA_LOWEJ 05P 0000000 0000000 0110010 0000000 0000000 0000000
10SZA_LOWEMU 05P 0010000 0000000 0000000 0000000 0010000 0000000
11SZA_LOWĄ 05P 0000000 0000000 0001100 0000000 0000000 0000000
12SZA_LOWYM 05P 0000110 0010000 0000000 0010000 0000110 0010000
13SZA_LOWI 05P 0000000 1000001 0000000 0000000 0000000 0000000
14SZA_LOWYCH 05P 0000000 0101010 0000000 0100010 0000000 0100010
15SZA_LOWYMI 05P 0000000 0000100 0000000 0000100 0000000 0000100
16SZA_LOWO 16O
17SZA_LE 00R 0000000 1001001 0000000 0000000 0000000 0000000
18SZA_LI 00R 0000000 0100000 0000000 0000000 0000000 0000000
19SZA_LÓW 00R 0000000 0100000 0000000 0000000 0000000 0000000
20SZA_LOM 00R 0000000 0010000 0000000 0000000 0000000 0000000
21SZA_LAMI 00R 0000000 0000100 0000000 0000000 0000000 0000000
22SZA_LACH 00R 0000000 0000010 0000000 0000000 0000000 0000000

Załóżmy, że mamy rdzeń SZA. Przypisujemy mu grupę nr 2R (sam fakt, że w nazwie grupy jest R oznacza, że to rzeczownik).
M1b - to oznaczenie jest widziane przez użytkownika (rzeczownik męski odmieniający się wg grupy odmiany 1b).
I teraz - z automatu dostajemy:
SZAL, SZALA, SZALOWI, SZALEM, SZALU, itd.
Oznaczenie 00R - to jest numer końcówki dla formy podstawowej oraz oznaczenie części mowy. Np. pozycja 12 ma oznaczenie 05P - to znaczy, że jest to przymiotnik, a jego formę podstawową znajdziemy pod pozycją 05 - czyli formą podstawową przymiotnika jest SZALOWY.
Pozycja 16O - to przysłówek SZALOWO.
Każda z pozycji może być w słowniku "wykluczona". Np. jeśli forma SZALA byłaby nie dobra (a dobra byłaby forma SZALU), to wyraz ten ma wykluczoną formę nr 1 (podobnie może być wykluczona forma 16).
Ponadto, każda z grup może występować w formie "skróconej" (np. niektóre rzeczowniki występują bez liczby mnogiej, wtedy mają włączoną odmianę skróconą).
Słownik to wszystko "widzi" i oprócz tego, że mamy informację o tym, czy wyraz jest w słowniku, to również wiemy, czy użyta forma jest używana (czy nie została wykluczona z wzorca odmiany).
Ciągi bitów za daną końcówką oznaczają przypadek. Np. pozycja 0 ma 1001000, to oznacza, że SZAL jest mianownikiem i biernikiem. Pozycja 5 ma 1001001 co oznacza, że to mianownik, biernik i wołacz.
Tych bajtów jest sześć i odnoszą się one do rodzaju męskiego w liczbie pojedynczej i mnogiej, potem żeńskiego i niejakiego.
Stąd np. pozycja 22 -> 0000010 w naszym przykładzie oznacza miejscownik liczby mnogiej.
Te kombinacje bitów pozwalają badać związki zgody i rządu. Jeśli dwa wyrazy (np. rzeczownik i przymiotnik) stoją obok siebie, to ich bajty muszą mieć przynajmniej jeden bit wspólny.

W ten sposób mamy rozpisane 255 różnych grup (w tym rzeczowniki, czasowniki, liczebniki, itd.). I jak wspomniałem mamy 76 tys. rdzeni.
Do każdego rdzenia można ponadto przypisać zestaw przedrostków (w sumie mamy 64 różne przedrostki).
Ponadto rdzenie mamy pogrupowane w różnych słownikach. Np. mamy osobno nazwy własne, osobno skróty wymagające kropki, osobno symbole z określoną pisownią w zakresie wielkich i małych liter.
Mamy bazę wyrazów nieodmiennych lub wyjątków z przypisanymi informacjami o części mowy, przypadku, liczbie, aspekcie, itp.
Mamy również słownik wyrazów obcych używanych w polszczyźnie oraz specjalny słownik błędów zawierający wyrazy często pisane błędnie, a także pary wyrazów: błąd->poprawny.
Mamy algorytmiczne rozpracowane połączenia liczebników (np. jeśli istnieje wyraz wieloletni, to istnieje również stopięćdziesięciopięcioletni i tego wyrazu już nie trzeba wprowadzać, on się sam "generuje").
To daje nam około 2,5 mln dobrych form wyrazowych oraz kilkadziesiąt tysięcy "wykluczeń" (tzn. słów, które możemy nie tylko określić jako "nieznane", ale dać ostrzeżenie "tu jest na pewno błąd").

Mamy też słownik synonimów z algorytmem pozwalającym na inteligentną podmianę słów. Jeśli np. chcemy w całym tekście podmienić jakiś wyraz na inny wyraz (np. synonim) i on jest w innym rodzaju (np. samochód->auto), to algorytm znajduje najpierw formę podstawową wyrazu odmienionego (np. samochodem->samochód), następnie sprawdza jaki to był przypadek (samochodem -> narzędnik), dalej znajduje synonim dla formy podstawowej samochód (w słowniku synonimów są rzecz jasna tylko formy podstawowe).
Załóżmy, że znajdzie synonim "auto". I teraz szuka narzędnika dla "auto". Znajduje "autem". I to proponuje do wymiany.
Ten sam algorytm jest wykorzystany do funkcji "Szukaj/wymień z uwzględnieniem odmiany" (uwaga, jeśli zdecydujecie się na testowanie, to w pole "Szukaj" trzeba wpisać formę podstawową szukanego wyrazu).

Słownik ma też dane i algorytmy dotyczące dzielenia wyrazów. Ale to inny temat. Jeśli jesteście zainteresowani, to dajcie znać, bo list się zrobił trochę długi :-)

Ten słownik jest zaimplementowany w Systemie Komputerowego Składu Dokumentów KOMBI. W tym pakiecie jest kilka programów, ale słownik jest podłączony konkretnie do programu KombiKor.

Można pobrać wersję 30-dniową pakietu z podanego niżej adresu i zobaczyć jak to do działa w praktyce:
https://kombi.3n.com.pl/download

Oczywiście prace nad programem nigdy się nie kończą. Pracuję właśnie nad instalką do nowej wersji. Ale ponieważ założyłem, że może zdecydujecie się pobrać i zobaczyć, to właśnie przed chwilą zamieściłem tę nową instalkę na serwerze (stara miała już półtora roku).
Tak więc z góry przepraszam za ewentualne niedociągnięcia (złożenie instalki to zawsze jest ból :-) - żeby wszystko było ze sobą zgrane). Dajcie znać jak coś będzie nie tak.
I jeśli traficie na jakiś dobry wyraz, którego nie ma w słowniku, to też będę wdzięczny za jego podanie. Język szybko się zmienia.

Oczywiście chętnie odpowiem na ewentualne pytania.

1 użytkowników online, w tym zalogowanych: 0, gości: 1