Mam tysiące list ciągów, a każda lista zawiera około 10 ciągów. Większość ciągów na danej liście jest bardzo podobnych, chociaż niektóre ciągi są (rzadko) całkowicie niezwiązane z innymi, a niektóre ciągi zawierają nietrafne słowa. Można je uznać za hałaśliwe odmiany łańcucha kanonicznego. Szukam algorytmu lub biblioteki, która przekonwertuje każdą listę na ten ciąg kanoniczny.
Oto jedna z takich list.
- Star Wars: Episode IV Nowa nadzieja | StarWars.com
- Star Wars Episode IV - A New Hope (1977)
- Star Wars: Episode IV - A New Hope - Rotten Tomatoes
- Oglądaj Star Wars: Episode IV - Nowa nadzieja online za darmo
- Star Wars (1977) - Greatest Films
- [REC] 4 plakat obiecuje śmierć przez silnik zaburtowy - SciFiNow
W przypadku tej listy ^Star Wars:? Episode IV (- )?A New Hope$dopuszczalny byłby dowolny ciąg pasujący do wyrażenia regularnego .
Przyjrzałem się kursowi Andrew Ng na temat uczenia maszynowego na Coursera, ale nie udało mi się znaleźć podobnego problemu.
nlp
similarity
information-retrieval
lakton
źródło
źródło
Odpowiedzi:
Jako naiwne rozwiązanie proponuję najpierw wybrać ciągi znaków, które zawierają najczęstsze tokeny na liście. W ten sposób możesz pozbyć się niepotrzebnego ciągu.
W drugim zdaniu głosowałbym większością głosów. Zakładając 3 zdania:
Przejrzałbym tokeny jeden po drugim. Zaczynamy od „Star”. Wygrywa, gdy zaczyna się cały ciąg. Wygra także „Wars”. Następny to „:”. Wygra również.
Wszystkie tokeny będą głosować większością do „Nadziei”. Następnym żetonem po „Nadziei” będzie albo „|”, albo „(” lub „-”. Żaden z nich nie wygra większością głosów, więc zatrzymam się tutaj!
Innym rozwiązaniem byłoby prawdopodobnie użycie Najdłuższej wspólnej podsekwencji .
Jak powiedziałem, nie myślałem o tym zbyt wiele. Więc może być znacznie więcej lepszych rozwiązań twojego problemu :-)
źródło
Najpierw oblicz odległość edycji między wszystkimi parami ciągów. Zobacz http://en.wikipedia.org/wiki/Edit_distance i http://web.stanford.edu/class/cs124/lec/med.pdf . Następnie wyklucz ciągi odstające na podstawie pewnego progu odległości.
Przy pozostałych ciągach możesz użyć macierzy odległości, aby zidentyfikować najbardziej centralny ciąg. W zależności od metody, której używasz, możesz uzyskać niejednoznaczne wyniki dla niektórych danych. Żadna metoda nie jest idealna dla wszystkich możliwości. Do swoich celów potrzebujesz tylko kilku heurystycznych zasad rozwiązywania dwuznaczności - tj. Wybierania dwóch lub więcej kandydatów.
Być może nie chcesz wybierać „najbardziej centralnego” z listy ciągów, ale zamiast tego chcesz wygenerować wyrażenie regularne, które przechwytuje wzorzec wspólny dla wszystkich ciągów nietypowych. Jednym ze sposobów na to jest synteza ciągu, który jest w równej odległości od wszystkich ciągów nietypowych. Możesz obliczyć wymaganą odległość edycji od matrycy, a następnie losowo wygenerować regularne, używając tych odległości jako ograniczeń. Następnie przetestujesz kandydujące wyrażenia regularne i zaakceptujesz pierwsze, które pasuje do ograniczeń, a także akceptuje wszystkie ciągi z twojej listy nietypowych. (Rozpocznij budowanie wyrażeń regularnych z najdłuższych popularnych list podciągów, ponieważ są to znaki nieoznaczone symbolami wieloznacznymi).
źródło