Оценка строки, основанная на том, как это по-английски
Я не уверен, как именно сформулировать этот вопрос, так что вот пример:
string1 = "THEQUICKBROWNFOX" string2 = "KLJHQKJBKJBHJBJLSDFD"
Я хочу функцию, которая будет оценивать string1 выше, чем string2, и миллион других бессмысленных строк. Обратите внимание на отсутствие пробелов, так что это символьная функция, а не слово за словом.
В 90-х годах я написал функцию подсчета триграмм в Delphi и заполнил ее триграммами от Хака Финна, и я подумываю перенести код на C или Python или добавить его в отдельный инструмент, но должны быть более эффективные способы к настоящему времени Я буду делать это миллионы раз, так что скорость хорошая. Я попробовал библиотеку Python Reverend.Thomas Beyse() и натренировал ее на некоторых строчках-заглавных буквах, но, похоже, между словами требуется пробел и, таким образом, возвращается оценка []. Я нашел несколько библиотек цепей Маркова, но они также, казалось, требовали пробелов между словами. Хотя из моего понимания их я не понимаю, почему так должно быть...
В любом случае, я делаю много криптоанализа, поэтому в будущем будут полезны функции подсчета, которые используют пробелы и знаки препинания, но сейчас мне нужны только ALLCAPITALLETTERS.
Спасибо за помощь!
5 ответов
Я бы начал с простой модели вероятности того, насколько вероятна каждая буква, учитывая предыдущую (возможно, нулевую, в начале слова) букву. Вы можете построить это на основе файла словаря. Затем вы можете расширить это, чтобы использовать 2 или 3 предыдущих буквы в качестве контекста, чтобы обусловить вероятности, если исходная модель недостаточно хороша. Затем умножьте все вероятности, чтобы получить оценку для слова, и, возможно, возьмите N-ный корень (где N - длина строки), если вы хотите нормализовать результаты, чтобы вы могли сравнивать слова различной длины.
Я не понимаю, почему цепь Маркова не может быть модифицирована для работы. Я хотел бы создать своего рода словарь текстовых файлов и прочитать его, чтобы изначально заполнить структуру данных. Вы бы просто использовали цепочку из n букв, чтобы предсказать следующую букву, а не из n слов, чтобы предсказать следующее слово. Тогда, вместо случайного создания письма, вы, вероятно, захотите извлечь вероятность следующей буквы. Например, если у вас была текущая цепочка "TH", а следующая буква была "E", вы бы пошли на свою карту и увидели вероятность того, что "E" последует за "TH". Лично я просто сложил бы все эти вероятности, пока проходил по цепочке, но как точно определить оценку по вероятности, зависит от вас. Вы можете нормализовать это для длины строки, чтобы позволить вам сравнивать короткие и длинные строки.
Теперь, когда я думаю об этом, этот метод предпочтет строки с более длинными словами, так как словарь не будет включать фразы. Опять же, вы можете заполнить словарь не только отдельными словами, но и короткими фразами с удаленными пробелами. Тогда оценка будет зависеть не только от того, насколько английскими являются отдельные слова, но и от того, насколько английские серии слов. Это не идеальная система, но она обеспечит стабильную оценку.
Я не знаю, как это работает, но Mail::SpamAssassin::Plugin::TextCat анализирует электронную почту и угадывает, какой это язык (с поддержкой десятков языков).
Здесь может помочь Индекс совпадений, см. https://en.wikipedia.org/wiki/Index_of_coincidence.
Для начала просто вычислите разницу IC с ожидаемым значением 1,73 (см. Википедию выше). Для расширенного использования вы можете самостоятельно рассчитать ожидаемое значение, используя несколько примеров корпусов языков.
Я думаю, что, может быть, вы могли бы применить некоторые идеи синтеза текста в речь здесь. В частности, если программа синтеза речи способна произвести произношение слова, это можно считать "английским".
Этап предварительной обработки называется преобразованием графемы в фонему и обычно приводит к вероятности преобразования строк в звуки.
Вот статья, которая описывает некоторые подходы к этой проблеме. (Я не утверждаю, что эта статья является авторитетной, так как это был просто высоко оцененный результат поиска, и у меня нет особого опыта в этой области.)