Определение того, насколько данная строка похожа на коллекцию строк

10

Я не уверен, принадлежит ли этот вопрос здесь, и я прошу прощения, если нет. Что я хочу сделать, так это разработать программный способ, с помощью которого я могу вероятностно определить, принадлежит ли данная строка «сумке строк». Например, если у меня есть сумка из 10 000 названий городов США, а затем у меня есть строка «Филадельфия», я хотел бы получить количественную оценку вероятности того, что «Филадельфия» - это название города США, основанное на названиях городов США, которые я уже знаю. Хотя я знаю, что не смогу отделить настоящие названия городов от поддельных названий городов в этом контексте, я бы по крайней мере ожидал, что такие строки, как «123.75» и «Быстрая рыжая лиса перепрыгнули через ленивых коричневых собак», исключены, учитывая какой-то порог.

Для начала я посмотрел на расстояние Левенштейна и немного обдумал, как это применяется к проблемам, по крайней мере, несколько похожим на ту, которую я пытаюсь решить. Одним интересным приложением, которое я нашел, было обнаружение плагиата. В одной статье описывалось, как расстояние Левенштейна использовалось с модифицированным алгоритмом Смита-Уотермана для оценки работ на основе того, насколько вероятно, что они были плагиатной версией данной базовой бумаги. Мой вопрос заключается в том, может ли кто-нибудь указать мне правильное направление с помощью других установленных алгоритмов или методологий, которые могут мне помочь. У меня такое чувство, что это может быть проблемой, которую кто-то в прошлом пытался решить, но до сих пор мой Google-фу не помог мне.

Эндрю
источник
Если у вас есть положительные и отрицательные примеры, вы можете попробовать подготовить классификатор. Для начала я бы попробовал вытащить несколько простых статистических данных, например, предложенных Ювалом Фильмусом.
Ник
Обратите внимание на этот связанный вопрос .
Рафаэль
Названия городов кажутся плохим примером; они повсюду, особенно в США. Здесь, поиск таблиц представляется наиболее эффективным способом. Ваша проблема более общая?
Рафаэль

Ответы:

5

Некоторые лучшие статистические данные, о которых нужно думать, - это анализ длины слова и граммы. Что касается длины слова, вы можете собрать статистику распределения длины слова по названиям городов и сравнить ее с длиной того, что вы получаете. Анализ граммы рассматривает распределение последовательностей из букв в тексте вашего образца (скажем, ). Оба подхода могут быть объединены.nn n = 2nnn=2

Учитывая эвристику, вы можете использовать вероятность, чтобы получить оценку, которая (надеюсь) будет выше для ваших выборочных данных, чем для другого текста. Чтобы определить разумный порог, вы можете выполнить перекрестную проверку. Выберите набор примеров фраз, которые не являются названиями городов. Разделите названия городов на две части: большую (скажем, 80%) и небольшую (скажем, 20%). Обучите свою модель большей части (то есть соберите статистику по большей части), а затем оцените свою модель по малой части и по выборке плохих фраз. Определите, есть ли разумный порог, который соответствует большинству названий городов, но только небольшое количество плохих фраз.

Юваль Фильмус
источник
Спасибо. Я начал смотреть на n-грамм, но не знал, был ли я полностью вне базы, поэтому я рад, что вы упомянули это. Длина слова тоже звучит интересно, и я не думал об этом.
Андрей
Вы можете добавить частоту символов к этому. В частности, от всего этого нужно избавиться. Одним из преимуществ является то, что такие частоты являются векторами чисел, которые можно обучать / распознавать в ряде статистических моделей.
Рафаэль
1
1N+1N