Сложное сравнение

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

Для начала поговорим о стратегии алгоритма. Мы могли бы здесь посчитать простое количество попаданий букв одной строки в другую, однако это исключает вероятность оценки сходства суффиксов и окончаний слов, как в последнем нашем примере с «эволюцией» и «конституцией». Судите сами.

эволюция

конституция

Если мы начнем перебирать индексы букв этих слов с «головы», сравнивать их последовательно [1, 2, 3, 4, 5…], то ни одного раза не получим совпадения:

э <> к, в <> о, о <> н, л <> c, ю <> т, ц <> и, и <> т, я <> у, «» <> ц, «» <> и, «» <> я.

Это плохо, поскольку для любого адекватного человека понятно, что слова похожи окончанием « -ция».

Очевидно, что алгоритм должен быть несколько сложнее простого последовательного перебора индекса для таких случаев.

Для решения этой проблемы, нам требуется провести комплексное сравнение. Мы будем сравнивать не конкретные позиции, а нахождение фрагментов одного слова в другом слове, меняя размер этих фрагментов от минимального к максимальному. То есть, сначала мы будем искать наличие букв по одной (э, в, о, л…); затем буквенных пар (эв, во, ол, лю, юц…); затем буквенных троек (эво, вол, олю, люц, юци, ция); четверок (эвол, волю, олюц, люци, юция); пятерок (эволю, волюц, олюци, люция); шестерок (эволюц, волюци, олюция); семерок (эволюци и волюция); и максимума – слова целиком (эволюция). Причем, чем больший фрагмент определяется попаданием, тем большее количество баллов мы должны присвоить за это попадание. Кроме того, нам следует учесть и разницу в длине строк.

Кстати, в данном случае, нам не принципиально соблюдение некой константы в виде получения процента, нам важен результат, который может быть выражен некоторым абстрактным числом баллов за количество попаданий и сравним его с другими результатами.

Программное решение этой процедуры может быть следующим.

Илл. 33. Процедура сложного сравнения двух строк.

Что происходит: первоначально, мы присваиваем переменной оценки сравнения (P) исходный балл (10 000), и оцениваем разность длины строк, за что также присваиваем различный размер «шага» оценки (step). В зависимости от величины разницы длины слов (L и L2) мы вычитаем эту разницу из первоначальной оценки (P). Затем происходит процесс приведения обоих слов к одинаковым условиям, – мы считаем их равными по длине, но если одно слово оказывается короче другого, то к нему присоединяется дополнительное число пустых символов-пробелов (S4).

Далее, происходит процесс сравнения с использованием циклов, описанный выше. И в завершении, мы вычитаем исходное количество баллов из полученной оценки.

В результате работы процедуры мы получаем оценку сходства слов «эволюция» и «конституция» в 908 баллов. Если же в качестве первого слова выступит «рыба», или «аргумент», оценка снизится до 0 баллов. Слово же «конституционный» поднимет оценку до 8 880. Конечно, это абстрактное число, однако в рамках столь же абстрактных координат оно дает стабильные сравнительные показатели сходства слов на естественном языке.

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

Теперь следует определиться, что делать в таком случае с предложениями. Для начала попробуем пилить их на слова и выводить в форме массива из отдельных слов. В таком виде обработка больших фрагментов текста значительно упрощается.

А чем разделяются слова в предложениях? Правильно, пробелами и пунктуацией. Мы приготовим универсальную процедуру, которая будет «распиливать» любое предложение на набор слов и складывать их в массив для вывода. Стратегия здесь довольно простая, – идти вдоль индекса предложения и используя маркер разделения (пробел) отделять очередное слово. При этом, мы не станем сохранять пунктуацию, – ведь она «создает шум»: в данном случае – это словарные конструкции, которых нет. Ведь фактически для программы слова «корова» и «корова,» будут двумя разными словами, разными наборами символов. Это нас не устраивает. Поэтому, помня о том, что нам еще следует обработать пунктуацию, выделим исключительно все слова в предложении. Так может выглядеть эта процедура:

Илл. 34. Процедура Justbreak «распиливает» предложение на отдельные слова и сохраняет его в массив с числом элементов j.

В процедуре Justbreak происходит обработка предложения, поступившего в переменную S в двух циклах Repeat. В ней, индекс слова будет контролировать переменная j, а индекс последовательного символа в предложении – переменная i. Первый цикл присваивает новое значение счетчику индекса слова командой inc (j). Условием выхода из цикла, сохраняющего слово, будет символ пробела, запятой, двоеточия, точки или превышение индекса i длины строки предложения. Внутри этого цикла мы добавляем очередной символ к текущему слову, если он соответствует условиям – не равен знаку пунктуации или пробелу. Кто-то может возмутиться, ведь процедура разбивает некоторые составные слова, вроде «кто-то», «как-то», «как-нибудь» и т. д. Но в данном случае мы все же отделим «мух от котлет» – выделим составные конструкции как слова по отдельности, но запомним, в какой конструкции пунктуации они находились.

Данный текст является ознакомительным фрагментом.