Распознавание осмысленного текста?

Question

[zooh]

Добрый день!


Возник такой вопрос: существуют ли известные механизмы, чтобы отличить случайный набор символов от более-менее литературного текста на заданном языке? В каком направлении копать? Пока придумал только набирать статистику по массивам «живых» текстов: частоты отдельных символов, двоек и троек, а потом считать коэффициент корреляции Пирсона. Кто хорошо рубит в матстатистике, может, подскажете более продвинутые методики анализа?

Answer 1

[YasonBy]

Ваша идея вполне имеет право на жизнь. Собственно, Вы изобрели метод N-грамм :)

Если хотите использовать что-то более сложное (стóит ли?), вот статья с обзором трёх методов (pdf, англ.) Подборку статей по теме можно найти здесь. На более популярном уровне, и на русском языке — здесь.

Сложность требуемого подхода зависит от Вашей задачи. Например, если важна точность, можно использовать цепи Маркова. То есть, берём «Войну и мир», и собираем статистику: как часто за последовательностью букв x₁…x_N-1 встречается буква x_N? N — порядка 3..4. Потом берём подопытный текст, пробегаемся по нему, перемножая вероятности. В результате получаем вероятность того, что подопытный является осмысленным текстом на русском языке.

Если же скорость важнее точности, можно заменить вероятности на булевы величины: встречается ли хоть раз в «Войне и мире» последовательность букв x₁…x_N?

Comments

[zooh]

Во, уже что-то, спасибо за ссылки! Метод я не то чтобы «изобрёл», он скорее скомпилирован из невнятных жвачек на форумах, обнаруженных беглой разведкой; теперь, имея название, можно уже более пристально изучить.

Answer 2

[rPman]

Случайный набор символов — это детектируется по словарям (немного прикрутить поддержку окончаний, приставок и т.п.), как я помню опенсорсные библиотеки проверки орфографии содержат необходимые алгоритмы и базы.

Выявление просто предложений на человеческом языке можно сделать статистическим анализом, но это на порядок сложнее и так же ничего не решает, так как осмысленный текст таким образом не выделишь…

Монстры вида Abbyy берут миллиардные гранты на разработку таких алгоритмов, боюсь у вас не на много больше шансов разработать успешные алгоритмы.

p.s. попробуйте понять, осмысленный ли это текст, это просто класика (взято тут, еще тут):

Родился на улице Герцена. В гастрономе № 22. Известный экономист. По призванию своему библиотекарь. В народе — колхозник. В магазине — продавец. В экономике, так сказать, необходим. Это, так сказать, система… эээ… в составе 120 единиц. Фотографируйте Мурманский полуостров — и получаете te-le-fun-ken. И бухгалтер работает по другой линии. По линии «Библиотека». Потому что не воздух будет, а академик будет! Ну вот можно сфотографировать Мурманский полуостров. Можно стать воздушным асом. Можно стать воздушной планетой. И будешь уверен, что эту планету примут по учебнику. Значит, на пользу физики пойдет одна планета. Величина — оторванная в область дипломатии — дает свои колебания на всю дипломатию. А Илья Муромец дает колебания только на семью на свою. Спичка в библиотеке работает. В кинохронику ходит и зажигает в кинохронике большой лист. В библиотеке маленький лист разжигает. Огонь будет… эээ… вырабатываться гораздо легче, чем учебник крепкий. А крепкий учебник будет весомей, чем гастроном на улице Герцена. А на улице Герцена будет расщепленный учебник. Тогда учебник будет проходить через улицу Герцена, через гастроном № 22, и замещаться там по формуле экономического единства. Вот в магазине 22 она может расщепиться, экономика! На экономистов, на диспетчеров, на продавцов, на культуру торговли… Так что, в эту сторону двигается вся экономика. Библиотека двинется в сторону 120 единиц, которые будут… эээ… предмет укладывать на предмет. 120 единиц — предмет физика. Электрическая лампочка горит от 120 кирпичей, потому что структура у нее, так сказать, похожа у нее на кирпич. Илья Муромец работает на стадионе «Динамо». Илья Муромец работает у себя дома. Вот конкретная дипломатия! «Открытая дипломатия» — то же самое. Ну, берем телевизор, вставляем в Мурманский полуостров, накручиваем, там… эээ… все время черный хлеб… Дак что же, будет Муромец, что ли, вырастать? Илья Муромец, что ли, будет вырастать из этого?

А ведь черные СЕОшники генерируют гораздо более интересные тексты.

Comments

[zooh]

О, мне вполне достаточно «выделения предложений на человеческом языке», и лучше бы статистическими методами. Боюсь, что словарный анализ будет сильно дольше работать. Мне бы хотя бы направление «раскопок» уяснить, я матстатистику в последний раз в вузе видел NN лет назад. Наверняка же какие-то типовые наработки есть, не хочется велосипед изобретать.