У меня есть тысячи списков строк, и каждый список имеет около 10 строк. Большинство строк в данном списке очень похожи, хотя некоторые строки (редко) полностью не связаны с другими, а некоторые строки содержат нерелевантные слова. Их можно считать шумными вариациями канонической струны. Я ищу алгоритм или библиотеку, которая преобразует каждый список в эту каноническую строку.
Вот один из таких списков.
- Звездные войны: Эпизод IV Новая Надежда | StarWars.com
- Звёздные войны. Эпизод IV - Новая надежда (1977)
- Звездные войны: Эпизод IV - Новая надежда - Гнилые помидоры
- Наблюдайте за Звездными Войнами: Эпизод IV - Новая Надежда Онлайн Бесплатно
- Звездные войны (1977) - Величайшие фильмы
- [REC] 4 плаката обещают смерть от подвесного мотора - SciFiNow
Для этого списка любая строка, соответствующая регулярному выражению ^Star Wars:? Episode IV (- )?A New Hope$, будет приемлемой.
Я посмотрел курс Эндрю Нг по машинному обучению на Coursera, но мне не удалось найти подобную проблему.
Ответы:
В качестве наивного решения я бы предложил сначала выбрать строки, которые содержат наиболее частые токены внутри списка. Таким образом, вы можете избавиться от ненужной строки.
Во второй фразе я бы проголосовал большинством. Предполагая 3 предложения:
Я бы прошел через токены один за другим. Начнем со «Звезды». Он выигрывает, так как все строки начинаются с него. «Войны» тоже победят. Следующим является ":". Это также победит.
Все жетоны получат большинство голосов до "Надежды". Следующим токеном после «Надежда» будет либо «|», либо «(» или «-». Никто из победителей не победит в мажоритарном голосовании, поэтому я остановлюсь здесь!
Другое решение было бы, вероятно, использовать самую длинную общую подпоследовательность .
Как я уже сказал, я не особо об этом. Так что, может быть, есть гораздо лучшие решения вашей проблемы :-)
источник
Сначала вычислите расстояние редактирования между всеми парами строк. См. Http://en.wikipedia.org/wiki/Edit_distance и http://web.stanford.edu/class/cs124/lec/med.pdf . Затем исключите любые строки выбросов на основе некоторого порогового значения расстояния.
С остальными строками вы можете использовать матрицу расстояний для определения самой центральной строки. В зависимости от используемого вами метода вы можете получить неоднозначные результаты для некоторых данных. Ни один метод не подходит для всех возможностей. Для ваших целей все, что вам нужно, это некоторые эвристические правила для устранения неоднозначностей - то есть выбрать двух или более кандидатов.
Возможно, вы не хотите выбирать «самый центральный» из списка строк, но вместо этого хотите сгенерировать регулярное выражение, которое фиксирует шаблон, общий для всех строк, не являющихся выбросами. Один из способов сделать это - синтезировать строку, которая равноудалена от всех строк, не являющихся выбросами. Вы можете определить необходимое расстояние редактирования от матрицы, а затем случайным образом сгенерировать регулярные значения, используя эти расстояния в качестве ограничений. Затем вы протестируете регулярные выражения-кандидаты и примете первое, которое соответствует ограничениям, а также примет все строки в вашем списке не-выпадающих. (Начните создавать регулярные выражения из самых длинных общих списков подстрок, потому что это не подстановочные знаки.)
источник