Вычисление вероятности того, что строка была рандомизирована? - питон

Question

это связано с вопросом, который я задавал ранее (вопрос)

У меня есть список строк, созданных вручную, например:

lucy87

gordan_king

fancy_unicorn77

joplucky_kanga90

base_belong_to_narwhals

и список рандомизированных строк:

johnkdf

pancake90kgjd

fancy_jagookfk

manhattanljg

---

То, что последний набор строк рандомизирован, так это то, что такие последовательности, как 'kjg', 'jgf', 'lkd', ....

Есть ли какой-нибудь умный способ отделить строки, содержащие эти явно рандомизированные строки, от толпы?

Я полагаю, что это играет большую роль в том факте, что некоторые символы с большей вероятностью будут размещены рядом с другими (например, 'co', 'ka', 'ja', ...).

---

Есть идеи по этому поводу? Kylotan упомянул Преподобный , но я не уверен, что его можно использовать для такой цели.

Помощь будет высоко ценится!

Answer 1

Это всего лишь мысль. Я никогда не пробовал сам ...

Создание фильтра Блума из хэширования каждой (пересекающейся) 4-буквенной последовательности, найденной в словаре. Проверьте строку, посчитав, сколько 4-буквенных последовательностей в строке не попадают в фильтр. Чем больше промахов, тем больше вероятность, что слово содержит случайный мусор.

Попробуйте настроить размер фильтра Блума и количество букв в последовательности.

Также обратите внимание (спасибо @MihaiD), что вы должны включить словарь имен, предпочтительно из нескольких языков, в фильтр Блума, чтобы минимизировать ложные срабатывания.

Answer 2

Какие оценки вы получите, если вы проведете строки через что-то вроде textcat ? (Я видел несколько разных реализаций TextCat; возможно, уже есть Python, а если нет, то это не сложный алгоритм - важны данные.)

Я думаю, что если вы удалите числа, первый набор строк будет ближе к "английскому" результату в TextCat, чем тот, в котором есть случайные элементы.

Насколько ближе и можно ли использовать данные TextCat - которые основаны на том, какие буквы обычно находятся рядом друг с другом в определенных языках - чтобы "пропустить" или "потерпеть неудачу" идущая строка хотя, нужно немного поэкспериментировать ...

Answer 3

Некоторое время назад я прочитал небольшую статью о генерации случайных имен, в которой они сделали следующее: они создали таблицу, содержащую информацию, на которую вы уже указали: «Я думаю, что это сильно влияет на тот факт, что определенные символы с большей вероятностью будут размещены рядом с другими ".

Так что они сделали, что они прочитали весь словарь и определили, какие буквы были помещены с большей вероятностью друг к другу. Я не знаю, сколько букв подряд они рассматривали. Может быть, вы должны попробовать больше, чем просто две последовательные буквы, скажем, что-то между 3 и 6.

Теперь я предлагаю вам составить такую ​​таблицу (возможно, в лучшем структурном представлении данных), которая содержит все «действительные» последовательные комбинации букв (и, возможно, их вероятность), и посмотреть, содержит ли (почти) ваше проверяемое имя такие «действительные» последовательные буквы.

Answer 4

Мне кажется, что вы пытаетесь написать код для распознавания определенного набора крошечных вещей, которые какой-то спаммер делает со строкой, чтобы пройти ваши фильтры. Что я не вижу, так это то, что мешает им после всей вашей тяжелой работы, 10-секундной настройки их алгоритма и победы над вашим новым фильтром.

Answer 5

Попробуйте использовать ванильный классификатор Байеса. Должно быть достаточно для общего случая.