Я не уверен, принадлежит ли этот вопрос здесь, и я прошу прощения, если нет. Что я хочу сделать, так это разработать программный способ, с помощью которого я могу вероятностно определить, принадлежит ли данная строка «сумке строк». Например, если у меня есть сумка из 10 000 названий городов США, а затем у меня есть строка «Филадельфия», я хотел бы получить количественную оценку вероятности того, что «Филадельфия» - это название города США, основанное на названиях городов США, которые я уже знаю. Хотя я знаю, что не смогу отделить настоящие названия городов от поддельных названий городов в этом контексте, я бы по крайней мере ожидал, что такие строки, как «123.75» и «Быстрая рыжая лиса перепрыгнули через ленивых коричневых собак», исключены, учитывая какой-то порог.
Для начала я посмотрел на расстояние Левенштейна и немного обдумал, как это применяется к проблемам, по крайней мере, несколько похожим на ту, которую я пытаюсь решить. Одним интересным приложением, которое я нашел, было обнаружение плагиата. В одной статье описывалось, как расстояние Левенштейна использовалось с модифицированным алгоритмом Смита-Уотермана для оценки работ на основе того, насколько вероятно, что они были плагиатной версией данной базовой бумаги. Мой вопрос заключается в том, может ли кто-нибудь указать мне правильное направление с помощью других установленных алгоритмов или методологий, которые могут мне помочь. У меня такое чувство, что это может быть проблемой, которую кто-то в прошлом пытался решить, но до сих пор мой Google-фу не помог мне.
Ответы:
Некоторые лучшие статистические данные, о которых нужно думать, - это анализ длины слова и граммы. Что касается длины слова, вы можете собрать статистику распределения длины слова по названиям городов и сравнить ее с длиной того, что вы получаете. Анализ граммы рассматривает распределение последовательностей из букв в тексте вашего образца (скажем, ). Оба подхода могут быть объединены.N n n = 2N N п = 2
Учитывая эвристику, вы можете использовать вероятность, чтобы получить оценку, которая (надеюсь) будет выше для ваших выборочных данных, чем для другого текста. Чтобы определить разумный порог, вы можете выполнить перекрестную проверку. Выберите набор примеров фраз, которые не являются названиями городов. Разделите названия городов на две части: большую (скажем, 80%) и небольшую (скажем, 20%). Обучите свою модель большей части (то есть соберите статистику по большей части), а затем оцените свою модель по малой части и по выборке плохих фраз. Определите, есть ли разумный порог, который соответствует большинству названий городов, но только небольшое количество плохих фраз.
источник