Wyodrębnij ciąg kanoniczny z listy hałaśliwych ciągów

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

PS Myślę, że termin, którego szukasz, to „kanoniczny”

— Sean Owen

Czy ciąg „najbardziej prawdopodobny” / „najbardziej konsensualny”, dla którego chcesz zidentyfikować wyrażenie regularne? Lub jeden z ciągów na liście?

— MrMeritology

@MrMeritology Nie szukam wyrażenia regularnego. W moim pytaniu pokazałem wyrażenie regularne, aby zilustrować, jak elastyczny jestem w rodzajach ciągów, które uważam za poprawne.

— Lakton

OK. Zatem odpowiedź, którą podałem poniżej, powinna dla ciebie zadziałać.

— MrMeritology

Czy byłoby to objęte NER (rozpoznawanie nazwanych podmiotów)?

— hippietrail

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:

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

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 :-)

— Pasmod Turing
ź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).

— MrMeritology
źródło