Искусственный интеллект. Строки, контекст и волны на Паскале - страница 23
Теперь протестируем готовую процедуру в следующей программе.
Илл. 31. Программа для тестирования процедуры LogicPercent.
Илл. 32. Пример работы процедуры LogicPercent.
По такому принципу можно обрабатывать большие массивы текста, добиваясь, к примеру, увеличения его уникальности.
Сложное сравнение
Предположим что нам необходимо выбрать из десятка слов два, наиболее похожих. Но что, если все они разные и простое сравнение не работает? Если самыми похожими окажутся, например, «ковровая» и «ковровый»? «Хлебный» и «хлебо-булочный»? «Эволюция» и «конституция»? В данных случаях поможет функция сложного сравнения сходства.
Для начала поговорим о стратегии алгоритма. Мы могли бы здесь посчитать простое количество попаданий букв одной строки в другую, однако это исключает вероятность оценки сходства суффиксов и окончаний слов, как в последнем нашем примере с «эволюцией» и «конституцией». Судите сами.
эволюция
конституция
Если мы начнем перебирать индексы букв этих слов с «головы», сравнивать их последовательно [1, 2, 3, 4, 5…], то ни одного раза не получим совпадения:
э <> к, в <> о, о <> н, л <> c, ю <> т, ц <> и, и <> т, я <> у, «» <> ц, «» <> и, «» <> я.
Это плохо, поскольку для любого адекватного человека понятно, что слова похожи окончанием « -ция».
Очевидно, что алгоритм должен быть несколько сложнее простого последовательного перебора индекса для таких случаев.
Для решения этой проблемы, нам требуется провести комплексное сравнение. Мы будем сравнивать не конкретные позиции, а нахождение фрагментов одного слова в другом слове, меняя размер этих фрагментов от минимального к максимальному. То есть, сначала мы будем искать наличие букв по одной (э, в, о, л…); затем буквенных пар (эв, во, ол, лю, юц…); затем буквенных троек (эво, вол, олю, люц, юци, ция); четверок (эвол, волю, олюц, люци, юция); пятерок (эволю, волюц, олюци, люция); шестерок (эволюц, волюци, олюция); семерок (эволюци и волюция); и максимума – слова целиком (эволюция). Причем, чем больший фрагмент определяется попаданием, тем большее количество баллов мы должны присвоить за это попадание. Кроме того, нам следует учесть и разницу в длине строк.
Кстати, в данном случае, нам не принципиально соблюдение некой константы в виде получения процента, нам важен результат, который может быть выражен некоторым абстрактным числом баллов за количество попаданий и сравним его с другими результатами.