Одно время я делал поиск по одному слову, поиск по регулярному выражению. А также поиск по ключевым словам. А потом заинтересовался нечетким поиском. Ну, т.е. чтобы можно было находить слова, близкие по звучанию и не учитывать, скажем, разные падежи, окончания. По идее, подобный поиск, конечно, уже давно осуществляют поисковые системы, типа Яндекса или Google. Не говоря уж об искусственном интеллекте (ИИ).

Это все здорово, но как искать информацию на сервере, т.е. у себя? Там, куда Яндекс может просто не попасть. Можно, конечно, установить ИИ у себя. Но, так думаю, что это будет по подписке, т.е. за оплату. А мне это невыгодно, т.к. подобные задачи возникают нечасто, хотя и систематически. Дело в том, что с годами накапливается все больше и больше интересной информации. И иногда уже забывается кое-что. Забывается иногда даже сам факт наличия информации о каком-то вопросе или предмете.

Ранее я выходил из положения при помощи своей простенькой справочной системы. Это - вебстраница, открываемая в браузере, сделанная по аналогии с Проводником Windows. Т.е. слева - ссылки (в том числе, сгруппированные в единые блоки), а справа - содержимое какой-нибудь ссылки, по которой был сделан клик. Да, это удобно, но когда объем документов там перевалил за многие сотни... я стал там слегка теряться.

Простой поиск слову (или его части), а также по регулярному выражению какое-то время выручал. И выручает до сих пор. Однако, со временем длительность такого поиска стала увеличиваться. Потом, иногда встречаются слова, близкие по синтаксису (и звучанию). И не всегда при поиске возможно указать точный синтаксис.

В общем, решил я сделать собственную поисковую систему

Есть, конечно, уже готовые решения. Например, в том же PHPStorm после нажатия Ctrl + Shft + F можно сделать (довольно быстрый) поиск по любым символам, фразам, присутствующим в файлах на (локальном, конечно же) сайте. Однако, во-первых, PHPStorm - достаточно тяжелая программа, он медленно загружается. Потом, вроде бы, он не позволяет осуществлять именно нечеткий поиск.

Есть также разного рода плагины для сайтов. Я с ними не работал, но люди пишут, что это все работоспособно. Видимо, примерно так и реализуется подобный поиск на сайтах. Когда начинаешь вводить некую фразу, а сервер в ответ выдает предполагаемые варианты - из состава тех, которые имеются у него. Честно сказать, НЕОХОТА мне связываться с чужими решениями.

Почему? Да, потому, что в итоге будут ограничения и неудобства. Например, выявится какая-нибудь уязвимость (так думаю, с вероятностью 80-90%). Потребуется обновление. А это - обновление и самого РНР и, быть может, даже обновление браузера. А ни то, ни другое мне вообще неинтересно. Ибо мне это нужно для РАБОТЫ (и т.п.), а не для того, чтобы обновлять... для того, чтобы потом обновлять (а потом - снова обновлять).

Вот те, кому нравится этот процесс - пусть обновляют хоть коженный день. А мне это неинтересно; мне нужно - чтоб работало и делало то, что нужно.

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

Как сделал

Честно говоря, описать довольно сложно, ибо логика там непростая. Любопытно, что даже сам слегка путаюсь, хотя везде, где надо и не надо, наделал хорошие комментарии (ну, как это у меня принято). В общем, попробую описать по этапам, как оно работает.

1. Вначале следует получить список всех файлов сайта. Каждому файлу присваивается свой уникальный числовой индекс, начиная с 1.

2. Затем нужно проиндексировать весь сайт. Все файлы, индексация которых разрешена (это, например, файлы с расширениями txt, html) и которые получили уникальный числовой индекс, просматриваются программой-индексатором, читается их содержимое.

3. Я взял необязательные русские слова, поиск которых точно не будет осуществляться. Это - предлоги, местоимения, союзы, частицы и междометия. Оказалось... наш русский язык-то достаточно конечен. И не столь уж много там таких частей речи. У меня получился список несколько превышающий 1200 слов. Возможно, я взял не всё. Так вот, эти слова удаляются из содержимого каждого индексируемого файла.

4. Затем содержимое индексируемого файла переводится в транслит. Это - один из этапов достижения нечеткого поиска.

5. Затем делается преобразование транслитированного слова при помощи функции metaphone языка PHP. Это очень удобная функция, она преобразует англоязычные слова и их укороченные "слоганы". Причем, такие, что они звучат очень сходно с исходным словом. Например, слово "время" после транслита и применения этой функции преобразуется в frmy. Точно также будет преобразовано слово "фремя" (хотя, такого слова в русском языке пока нет). Слово "каталог" преобразуется в ktlk. Эти преобразованные слова я называю метафонами.

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

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

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

7. А далее, собственно, сам процесс индексации метафонов. Здесь - два основных пути. Либо использовать файлы с надлежащей разметкой внутри них (в том числе, бинарные файлы). Либо - использовать "естественный" способ индексации, т.е. саму файловую систему операционной системы (это я сам придумал). Можно еще, конечно, использовать и базы данных. Но... "это" мне как-то неохота применять, по крайней мере, в силу высокой длительности запросов. Да и в силу уязвимостей. Для себя я такое использовать не буду. Вот для кого-нибудь, кто согласен, кому нравятся базы данных - на здоровье.

В общем, остановился на втором варианте. Как он выглядит?

Есть общий каталог под названием metaphones. В нем создаются каталоги с именами в 1 символ, сообразно символам того или иного метафона. Но, для двух ПОСЛЕДНИХ символов каждого метафона каталоги не создаются, эти символы записываются в файл под названием 1.txt. Например, для метафона frmy будет сформирован каталог с именем f, в нем будет каталог с именем r, а в этом каталоге будет файл 1.txt, в котором будет присутствовать строка my. Ну, за ней будут присутствовать индексы (см. п. 1) соответствующих файлов, из слов которых был получено этот метафон. Например, вот строка для указанного метафона:

Строка индексов для метафона frmy (часть индексов я удалил)

Каждое число - это соответствующий индекс. Это значит, что данный метафон имеется в файлах, имеющих индексы 677, 9, 10, 34, ну, и т.д. Чисел этих может быть довольно много.

Относительный путь к файлу, в котором находится эта строка, имеет вид \metaphones\f\r\ 1.txt.

Честно говоря, поначалу я создал систему БЕЗ таких строк. В ней путь имеет примерно такой вид:
\metaphones\f\r\m\y.txt. А в этом файле присутствуют только индексы (числа). Но, как оказалось, эта система будет хороша, если файлов на сайте будет весьма много (от 100 тысяч). Вот тогда она покажет свои лучшие стороны. А в моем случае оказывается, что объем, занимаемый индексными файлами на диске, превышает объем исходных файлов (с расширениями txt, html) чуть ли не на ДВА порядка.

Отчего? От того, что в Windows, даже если в файл записано всего лишь несколько байт, он все равно будет занимать на диске 4 кБ. Т.е.дисковое пространстов будет тратиться попусту. Другое дело, если индексов будет много и тогда в практически каждом индексном файле будет не несколько (десятков) байт, а большое объем индексов. Но, повторюсь, это (пока) не в моем случае.

Примерная структура каталогов (в Проводнике Windows)

Вот по этому алгоритму индексы слов-метафонов распределяются по файлам 1.txt, находящихся в соответствующих каталогах. И вот как оно примерно выглядит.

Конечно, таких каталогов будет множество, многие тысячи. НО, не сотни тысяч. Потому как русский язык - это достаточно ограниченная совокупность слов, хотя и очень большая. Но, все равно не бесконечен он. Поэтому рано или поздно, при увеличении числа индексируемых файлов (с контентом) новые каталоги больше не будут образовываться. Да и их общее число можно оценить теоретически.

Известно, что в английском алфавите присутствует 26 символов. Т.е. 26 (точнее, 27, если учитывать еще 0) каталогов верхнего уровня. В каждом из них может быть не более 27 каталогов второго уровня. И т.д., вплоть до 5-го уровня (число символов функции metaphone по умолчанию.

Тогда общее теоретическое максимальное число каталогов составит

27¹ + 27² + ... + 27⁵ ≈ 1,5*10⁷.

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

Впрочем, это - теоретическое число, на самом деле максимальное число файлов и каталогов будет гораздо меньше. Например, в русском языке есть слово "время", но нет слов "ревмя", "емярв" и т.п. Так, индексация слов из русского словаря ru.dic привела к созданию не более 14 тысяч каталогов. Их хватит, чтобы проиндексировать любые слова, имеющиеся в русском языке. Ну, а неправильных слов, типа "емярв", едва ли будет много. Поэтому фактическое число каталогов будет порядка на три меньше, чем теоретическое. Что, видимо, вполне приемлемо даже для не слишком мощного компьютера.

Что сказать? Одна тысяча файлов индексируется примерно за 10-15 минут. Т.е. за час будет индексировано примерно 5-10 тыс. файлов. НО - это у меня, на РНР 5. Да и компьютер у меня, скажем так, далеко не самый быстродействующий. Если же использовать РНР 8, то там быстродействие примерно в 10 раз выше. Ну, а если - еще и современный сервер, то вместо 10 минут получится несколько секунд.

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

8. Далее - интерфейс. Например, требуется найти все файлы сайта, содержащие или одновременно два слова "время, каталог", или слово "мир". Т.е. получается логическое выражение:

время && каталог || мир

Эти ключевые слова транслитируются, затем метафинизируются по тому же самому алгоритму, что и при индексации. Для удобства, чтобы каждый раз не переключаться на латинские буквы, я сделал возможность использования русскоязычных логических операторов И, ИЛИ. Т.е. логическое выражение может быть записано и так:

время и каталог или мир

Или даже так, еще проще:

время каталог или мир

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

В общем, эта фраза идет из браузера на сервер. Там она разбирается, анализируется, ищутся возможные ошибки (не знаю уж, насколько внимательно и полно я предусмотрел их обработку). Затем метафонизируется, получится вот что:

frmy&&ktlk||mir

9. Ну, а потом начинается поиск отдельных метафонов (frmy, ktlk, mir) в каталогах и файлах 1.txt, с учетом путей к ним (см. выше). Если соответствующая строка в каком-то из них есть, значит, все индексы, идущие, например, за метафоном frmy, обозначают индексы файлов, в которых присутствуют слова, метафон из которых соответствует frmy.

Сложно, но, что поделать. Это не на Laravel каком-нибудь ахинеей заниматься.

10. А дальше я придумал такой способ. Я заменяю метафоны в логическом выражении на соответствующие логические переменные. Пытаюсь найти файл 1.txt, в котором может присутствовать строка из 2-х последних символов метафона (например, строка my). Найти этот файл, если он есть, очень быстро. Нужно лишь взять путь вида \metaphones\f\r\ (где f, r являются первыми символами метафона) и добавить к нему 1.txt. Проверка наличия/отсутствия такого файла делается практически мгновенно. Это зависит не столько от языка PHP, сколько от быстродействия (ядра) операционной системы. Уж быстрее едва ли что есть, разве что Assembler.

Если такой файл имеется, также если последняя часть метафона (его последние 2 символа) присутствует этом файле, то считываем соответствующую строку (вида my|;677;9;10;34;48;. В ней присутствуют индексы файлов сайта, в которых имеется ключевое слово, метафон которого имеет вид frmy.

И вот тогда в логическом выражении для конкретного индекса (например, для индекса 677) вместо метафона я подставляю логическое значение true (1).

Иначе - false (0). Это если либо нет такого файла, либо в таком файле нет подобной строки, начинающейся с my.

Аналогично поступаю для других искомых ключевых слов.

В результате, вместо

время && каталог || мир

получается что-то вроде

1 && 1 || 0

Это тогда, когда слова время, мир присутствуют в некоем файле, имеющем индекс, например, 677; а вот слова мир в этом файле нет.

11. Таким же образом анализируются все остальные индексы, для каждого из искомых ключевых слов. Например, для слова каталог (метафон ktlk) в индексном файле 1.txt имеется строка с соответствующим множеством индексов:

lk|;677;11;30;256;

Поэтому для индекса 677 это слово в логическом выражении будет заменено на true.

В итоге, для каждого индекса (из множеств индексов) составляется логическое выражение.

12. Ну, а получающееся логическое выражение, для каждого индекса, оценивается при помощи функции eval. Если оно дает результат true, значит, искомые ключевые слова, с учетом данного логического выражения, имеются в файле сайта, имеющем соответствующий индекс (в данном случае, 677). Если получилось false, значит логическое выражение, содержащее искомые ключевые слова, не выполняется для этого файла.

13. И, наконец, дело за малым: найти файлы, соответствующие "удачным" индексам (т.е. таким, которые соответствуют файлам сайта, для которых выполняется логическое выражение с ключевыми словами). Это - легко и быстро, т.к. соответствующей перечень имеется в файле files.txt.

14. Напоследок, нужно вывести найденные имена "удачных" файлов на экран. Выводить частями, например, по 30 имен за раз.

Так что вот, вполне можно обойтись без использования баз данных

Ибо делается-то ОДИН раз. Даже лучше, чем базы данных, мне так кажется.

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

О качестве поиска

Качество хорошее, если говорить о поиске с точным соответствием. Если файлы с контентом проиндексированы, то поиск выполняется очень быстро.

А вот если говорить именно о нечетком поиске, то качество, конечно, не идеальное. Т.е. вместе со словом "время" найдутся, например, слова "фремя". Вместе со словом "результат" найдется слово "резульдад". И т.д. Т.е. поиск именно по схожести звучания (произношения), а не синтаксически близкие.

Видимо, помимо функции metaphone, стоит применить и другие подходы. Например, на основе вычисления расстояния Левенштейна.

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

Вероятно, от метафонизации придется уйти в другое решение. Пока думаю об использовании готового словаря русского языка. В частности, словаря, используемого браузером Firefox. Идея в том, что, например, если ввести ключевое слово "бежать", то будет осуществляться также поиск слов "бежит", "бегут", "бежала" и т.д. ОДНАКО(?), как быть, если при поиске ввести слово "бежит"? Как при использовании словаря искать те же самые слова ("бежать", "бежали", "бежала" и пр.)? Пока так и не пойму...

Кстати, насчет искусственного так называемого "интеллекта"

Открыв файлы словаря русского языка от браузера Firefox (в частности, файл ru.aff), я обнаружил там нечитаемые слова, типа ЪБФШУС, ЦХФУС. Я-то не знал, что это такое. Смотрел в интернете - не нашел. Потом спросил яндексовую Алису. Детально, подробно сформулировал вопросы. Она отмечала, мол, кодировка неправильная, убедитесь, что эти файлы закодированы в правильной кодировке и должна быть, мол, UTF-8. Причем, про эту кодировку она несколько раз отвечала очень убежденно.

Мой вопрос и ответ Алисы (частично сокращен, оставлено главное).

Для таких случаев есть выражение: "лютая дичь".

Хорошо хоть, Алиса дала ссылки, на основе которых формулировала свой "ответ". Эти ссылки оказались более полезными.

И если, мол, эти файлы у вас не в этой кодировке, то это, типа того, ошибка, перекодируйте их в UTF-8. Или замените их на правильные файлы. ВСЕ, более я ничего по сути от нее добиться не смог.

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

Кодировка... Уже потом, на одном онлайн-сервисе проверки кодировки, путем подбора, выяснил, что это, оказывается, просто-напросто русские слова в кодировке KOI8-R, но распознанной как Windows-1251. А UTF-8 тут вообще ни причем. И уж потом в этом файле, в самом, начале я вдруг обнаружил SET KOI8-R (Алиса об этой строчке, естественно, помалкивала). Видимо, это и есть обозначение кодировки этого файла (которую я вначале определил эмпирическим путем).

Это я уж так, просто попутно. Это - в сторону тех, кто ныне трезвонит о "больших возможностях" искусственного интеллекта. Совершенно не понимая, где звон и откуда он. Ладно, если это - таксист, сантехник, а то и госдумовец, кремлёвец, член совета федерации и/или вообще наркоман с алкогольным синдромом. Но, когда эту ахинею начинают нести... программисты... То сразу ясно, что это - даже не просто дураки, а, попутно, еще и бездельники. Которые практически ничего серьезного сами не сделали и неспособны сделать. Вот они и восторгаются этим самым AI.

Почему? Потому, что они настолько недоразвиты, настолько ограниченные и беспросветные, что на их-то фоне даже искусственный интеллект является как бы умным и знающим, поэтому (и только поэтому) они и восторгаются им. И готовы применять его везде. НО: это только на их фоне, на фоне этих разных многочисленных недорослей и дураков. Их уже ничего не вылечит, туда им и дорога.

Почему - не вылечит? Потому, что там НЕЧЕГО лечить. НЕТУ там ничего такого, что способно выздороветь. НЕ-ТУ.

Это касается "таких" и рядовых программистов, и их руководство. А всем остальным скажу так: БОЖЕ УПАСИ доверять искусственному интеллекту мало-мальски серьезную работу. Иначе он ТАКОЕ натворит, что потом годами придется расхлебывать. Например, в моем случае искусственный интеллект перекодировал бы файлы русского словаря в кодировку UTF-8 и тем самым сломал бы проверку русской орфографии в браузере, сделав ее не работающей.

Ну, а те, кто пытается внедрить искусственный интеллект еще и в систему обучения - это, на мой личный взгляд, тяжкие государственные преступники и/или полностью сумасшедшие, с медицинским диагнозом не ниже "дебил". Этих людей (всех таких, не делая скидок) следует изолировать от общества. Особенно тех, кто обладает высокой властью.

Вот она, эта программа.

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

Версия 2.0

В этой версии я реализовал нечеткий поиск (пока - только для русского языка). В планах - сделать и английский поиск, аналогично. Т.е. это поиск слов с разными окончаниями. Например, обычным поиском будет найдено слово "работа". Тогда как нечеткий поиск найдет соответствие следующему логическому выражению:

(работа || работе || работой || работою || работы || ...)

То же самое - для глаголов, прилагательных. Если обычный поиск длится, скажем, десятую долю секунды, то нечеткий длится 3...15 секунд, в зависимости от слова. Т.е. нечеткий поиск длится дольше на 1-2 порядка. Но, зато находит слова, примерно как Яндекс или Google. Долгий он из-за длительной (надеюсь, временно) работы со словарем.

Как сделал

Разумеется, уже давно кем-то используются готовые алгоритмы. Я с ними не знакомился (даже не смотрел вообще), решил сделать полностью по-своему.

Собственно, использовал предыдущую версию своей программы, но к ней добавил работу со словарем русского языка. Взял я его из браузера, 36-го Firefox.

На всякий случай. Вроде бы, в зависимости от версии этого браузера, формат словарей там - разный. Поэтому вполне возможно, что в какой-нибудь 100-й версии Firefox словарь будет выглядеть иначе, чем в 36-й версии. Поэтому у себя на Гитхабе я приложил файлы словаря тоже.

Эти файлы состоят из ru.dic (собственно, словарь русского языка) и ru.aff - словарь суффиксов (точнее, окончаний). Словарь нужен для того, чтобы найти всевозможные формы слова, с учетом окончаний. В частности, с учетом времен, падежей, родов, определенной/неопределенной форм (для глаголов), страдательного залога.

Так вот, получение этих всевозможных форм для одного слова у меня составляет примерно 3-4 секунды. Это, конечно, очень много. Ведь в том же Firefox проверка грамматики (в режиме contenteditable) делается практически мгновенно.

Причина (пока) в том, что файл словаря - довольно большой, там около 150 тыс. строк - слов. Так вот, перебор в этом словаре занимает много времени. Проблема еще в том, что слова там расположены вообще не по алфавиту. Поэтому поиск, например, методом бисекции (начиная с середины файла, потом половину делим еще на две части и т.д.) не получится. Не знаю, почему там не по алфавиту. Может, так задумано зачем-то.

Видимо, для ускорения работы придется как-то индексировать этот словарь. Пока даже не пойму, как именно. Вероятно, можно использовать ту же самую, мою систему индексации, в каталоге metaphones. Только имена файлов сделать не 1.txt, а, например, 1.dic. Если так сделать, поиск будет практически мгновенным даже при гораздо большем объеме словаря. А расход дисковой памяти возрастет несущественно. Оперативной памяти - также довольно мало расходуется.

Единственная проблема - это то, что образуется множество (теоретически - сотни тысяч, даже миллионы) вложенных каталогов. Что интересно, их удаление из корзины Windows занимает достаточно времени; даже при том, что фактически их объем может составлять, скажем, 2-3 МБ. Однако, пока они спокойно находятся на жестком диске, особых проблем нет. Все-таки, для системы NTFS это - мелочи (в отличие от FAT).

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

1. Идея - использовать в индексных файлах разметку. Типа, как на "кластеры".

А чтобы они не занимали на диске много места - архивировать их и каждый раз разархивировать (сразу в оперативную память), если возникла потребность в именно конкретном файле. Ведь при поиске потребуется, быть может, лишь несколько файлов, а не все. Остальные будут спокойно лежать архивированными и не занимать много места. Тем более, есть в РНР функции работы с архивами, например, с файлами gz. Правда, пока я ними не работал.

2. Или, как вариант, возможно, читать словарь в массив, делать некие маркеры, разделяющие группы слов по алфавиту (для этого придется таки отсортировать словарь). Чтобы массив НЕ перебирать по одному элементу, а сразу переходить к нужной группе слов, исходя из ее маркера-индекса. Перечень этих маркеров тоже хранить в каком-то (тоже индексном) файле. Правда, если для этого использовать двумерный (не одномерный) массив, это может замедлить работу. По идее, если организовать 100 маркеров, получится ускорение поиска в словаре примерно в 100 раз. Но, для этого придется отсортировать словарь.

3. А то и, как вариант, реализовать ТУ ЖЕ САМУЮ структуру, по типу структуры каталогов, только среди элементов массива. Получится, конечно, многомерный массив. Например, нужно найти слово "каталог" (метафон - ktlk). Пусть массив имеет имя М. Тогда, условно, $М['k']['t']['l']['k'] = 'K'. Это будет соответствовать следующей строчке из словаря: каталог/K. Если же такой строчки не было бы, то этого элемента массива тоже не было бы. Очень удобно, быстро и просто. Однако, когда я опробовал этот вариант, то в итоге массив занял 130 МБ с лишним, после чего РНР прекратил работу. Т.е. этот вариант, видимо, оптимален для достаточно мощных компьютеров (типа Яндексовских или Google-ских). Но, не для меня. Мне пришлось использовать другой вариант.

Вот она, версия 2.0.

Версия 2.1

Решил я пока остановиться на 2-м варианте, с маркерами. Содержимое файла-словаря отсортировал и перевел в нижний регистр. Честно говоря, обычные функции PHP работают на порядок быстрее, чем те, что не учитывают регистр (с символом i).

Почему? Я не вникал пока в реализацию. Но, похоже, дело в том, что они при поиске производят замену всех символов на нижний (или верхний) регистр. А это - довольно долго. Ведь кириллические символы "а" и "А" - это совсем разные символы. Это вовсе не "один символ, просто в другом регистре".

Почему такой вывод? Потому, что делал соответствующие эксперименты. Так вот, время, затрачиваемое на преобразование в один регистр и последующий поиск обычной функцией, примерно равно времени на поиск безрегистровой функцией.

И едва ли будет потребность в поиске с учетом регистра (исключение составляет поиск неких особенных одиночных слов). Но, для этого у меня давно сделан другой поиск. Он - без индексации, поэтому на порядок дольше.

Вот что примерно получается в файле маркеров:

ак:1-1424:1424:7-34382
ал:1425-3876:2452:34382-91916
ат:3877-4211:335:91916-99345
бк:4212-6956:2745:99345-162462
бл:6957-8820:1864:162462-203453
бт:8821-9570:750:203453-218549
вк:9571-12949:3379:218549-293380
вл:12950-16817:3868:293380-385128
вт:16818-20933:4116:385128-485841 
...

Объем этого файла занимает 3 кБ с лишним, что вполне даже приемлемо. Меньше 4096 байт (с учетом того, что работаю в Windows, где размер файла на диске составляет на менее указанного числа байт; на моем компьютере, по крайней мере).

Маркер "ак" соответствует тем файлам из словаря, первые буквы которых не превышают "ак". Т.е. это слова "акт", "активно", "аист", "адовый" и т.д.
Маркер "ал" соответствует тем файлам из словаря, первые буквы которых выше "ак", но не превышают "ат". Это слова, типа "алый", "аметист", "априори", "атрофированный".
Маркер "ат" соответствует тем файлам из словаря, первые буквы которых выше "ат". Это слова, типа "афера", "аутодафе", "ахинея".

Последние цифра справа - это номера (диапазоны номеров) позиций (в байтах) в отсортированном файле-словаре (ru.dic), на которых содержатся соответствующие слова. Например, слова из первой вышеупомянутой группы находятся на позициях из диапазона 7-34382.

Слева от этих цифр находятся, числа, указывающие количества строк (слов) в файле-словаре, соответствующие указанному маркеру (в начале строки). Например, для буквы "а" они составляют: 1424, 2452, 335. Числа различаются примерно на порядок. Т.е. время поиска будет самым коротким для слов, соответствующим маркеру "ат", а самым длинным - для маркера "ал". В целях оптимизации, возможно, следует подобрать другие буквы. Например, "и"("к"), "п" (вместо "к"("л"), "т").

Однако, даже и сейчас, в результате, если ранее (в версии 2.0) поиск слова в словаре составлял секунды 2...3, то теперь - 0,18 секунд. Теперь это время уже не является лимитирующим. Лимитирующее время (0,23 сек.) тратится на поиск имени файла и получение тех имен файлов, которые имеют индексы, содержащиеся в том или ином файле с именами 1.txt (расположенных в каталогах metaphones). Вероятно, это потому что пока он читается построчно. Возможно, если читать его и сразу преобразовывать в массив (по частям, для больших файлов), это время снизится примерно на 1-2 порядка.

Если точнее, оказалось, что при использовании массива время составило всего лишь (примерно) 0,006 секунд. Т.е., как и ожидалось, экономия времени составила в 30 раз. Т.е. даже если файлов на (локальном) сайте будет не пара тысяч, а миллион, соответствующее время будет 6 секунд... что в целом, приемлемо. Ну, а если еще и здесь сделать индексирование, то время снизится на 1-2 порядка. Так что возможности, пожалуй, практически неограниченные, даже на моем компьютере, даже на PHP 5. Ну, а уж на сервере, даже на сравнительно маломощном хостинге, поиск будет и вовсе "летать", т.е. выполняться практически мгновенно. Никакие базы данных, как мне видится, не угонятся (здесь я могу ошибаться).

Возможно, еще быстрее (раза в 2...4) будет, если использовать соответствующую процедуру, написанную на С/С++. Я пока не проверял. Хотя, PHP, на самом деле, не намного медленнее, чем С++. Потому что многие его команды представляют собой, всего-навсего, обертки над аналогичными командами С/С++. При многократном повторении (например, в циклах) команды кэшируются и разница во времени (по сравнению с С/С++) становится уже не столь заметной. Ну, а быстрее С/С++ - только Ассемблер или программы, изначально написанные в машинных кодах.

Собственно, то и дело подтверждается тот факт, что в свое время, лет 10-15 назад, я не ошибся в выборе языка программирования. Не стал увлекаться разными java и Питонами.

Т.е. даже для больших файлов есть смысл все-таки использовать массив, пусть даже по частями.

Также немало времени занимает блок оценки логических выражений при помощи eval - целых 0,12 сек. Возможно, там тоже надо что-то оптимизировать.

Что сказать? Общее время на поиск слов (одного или нескольких, с учетом логического выражения) составляет, на моем компьютере, примерно 0,6 секунд; ну, плюс-минус. Среди примерно 1000...2000 файлов (txt, html). Общий их объем составляет где-то 30 МБ.

Кстати, программа PhpStorm при каждом запуске производит индексирование файлов (для сайтов, которые есть на сервере). Это дает возможность быстро найти любое слово/фразу. Любопытно, что время, затрачиваемое ею на индексирование, - примерно такое же, как и у меня, т.е. несколько секунд (максимум, секунд 10). Хотя, PhpStorm написана на java+Kotlin, а у меня тут - PHP. Время на поиск - примерно такое же, но, пожалуй, пониже.

Так думаю, задержка связана с тем, что, во-первых, РНР 5, а, во-вторых, - что Denwer. Если же это все запустить на PHP 8 и без Denwer, то скорость возрастет примерно на порядок. Возможно, будет работать быстрее, чем PhpStorm. Правда, там можно искать ЛЮБОЕ слово, в том числе, содержащее спецсимволы, английские буквы и цифры.

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

Примечание. Похоже, в РНР 8.0 ухудшена работа функции mb_check_encoding(). В частности, она стала способна "определить" кодировку текста как cp1251, хотя на самом деле текст закодирован в utf-8. Тогда как РНР 5.3 таких проблем нет.

Хммм... А не за счет ли подобных ухудшений в новых версиях РНР повысилось быстродействие??... Так я посмотрю-посмотрю, да и останусь на старом-надежном РНР 5.3...

Вот она, версия 2.1.

Версия 2.2

Как я решил решить проблему слишком длительного поиска слов и их суффиксов в файле-словаре. Вначале все раздумывал о некоей функции, которая сопоставляла бы словам те или иные (большие) числа. Может, даже сделать аналитическое представление ее и потом быстро вычислять (приближенные) номера позиций соответствующих слов, в зависимости от букв, содержащихся в слове. Что-то типа корреляции-регрессии. Для ускорения поиска можно было бы применить какой-нибудь метод Ньютона-Рафсона... Но, это придется хранить информации не намного меньше, чем сам объем словаря. Как-то не очень. Да и, честно говоря, если говорить о функции, то там будут коэффициенты, члены. А операции сложения, не говоря уж об умножении и делении - достаточно длительные. По сравнению с логическими. Быстрее выполнить несколько десятков логических операций сравнения (в процессе перебора), чем одну операцию умножения.

В языке С/С++ длительности разнятся на 1-2 порядка. Вероятно, в РНР - примерно так же.

Еще мне думалось применить метод бисекций. Т.е. взять половину массива содержимого словаря; затем от той части, которая, возможно, содержит искомое слово, опять взять половину. И т.д. До тех пор, пока не останется 5-10 строк (а в них уже искать прямым перебором). Всего таких делений потребуется не более 15. Операции эти будут делаться очень быстро, т.к. это - всего-навсего перемещение указателя в файле-словаре (точнее, в соответствующем массиве)... Впрочем, перемещение указателя в файле будет тоже быстрым. Т.е. даже необязательно читать его в массив.

Решил я в итоге проиндексировать словарь. Индексацию делать в тех же самых файлах 1.txt. Чтобы не плодить лишние файлы. Да и для удобства. Точнее, в них оставлять признаки того, что соответствующие слова (с учетом их метафонизации) присутствуют в файле-словаре. Примерно так:

lk:1|;677;11;30;256;

Здесь символы :1 указывают на факт присутствия, если у словарного слова нет индекса. Если в словаре этому слову задан суффикс (например, BL), то будет выглядеть примерно так:

lk:/BL|;677;11;30;256;

Ну, а если нет такого слова в словаре (метафон которого заканчивается на две последние буквы lk), значит, будет по-старому, как обычно:

lk|;677;11;30;256;

Это - достаточно длительная процедура. Поэтому проводить ее лучше не при индексации содержимого файлов сайта, а отдельно, в процессе просмотра всех слов словаря, его сортировки и, как результат, установки признаков присутствия в соответствующих файлах 1.txt. Можно даже заранее провести ее, а потом уже делать индексацию файлов. Я ее (пока) совместил с процедурой индексирования имен файлов.

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

В результате, время, требуемое для получения массива всевозможных форм слова (с учетом окончаний из файла ru.aff), снизилось примерно в 3-5 раз. Не на порядок, конечно, но хоть так. Сейчас оно у меня составляет где-то 0,12 секунд. А для 10 слов (в составе логического выражения) соответствующее время составит где-то всего лишь 0,2 сек. А не 1,2 сек. Дело в том, что это время, в зависимости от числа искомых слов, увеличивается нелинейно, причем, чем больше слов, тем слабее тем прироста времени. Т.е. зависимость довольно слабая, типа логарифма. Удивительно, но факт. Видимо, это связано с кэшированием функций в языке PHP. Одно дело, когда функция вызывается для получения разных грамматических форм одного слова, только один раз. Другое дело - когда для 10 слов она, уже будучи кэшированной, вызывается 10 раз подряд.

Основная проблема: почему-то иногда создаются заведомо неверные грамматические формы, наряду с верными. Пока я так и не понял, почему. Для некоторых слов. А для каких-то слов получается слишком много форм. Например, для слова "поле" вот какие формы получаются:

поле, полями, полям, полях, поля, полей, полю, полем, пол, полу, полом, пола, поль, поло, полы, полой, полою, полами, полам, полах.

Т.е. одновременно идет речь о таких начальных словах, как "поле", "пол", "пола". Ибо программа не понимает смысла. Для нее слово "поле" - это именительный падеж слова "поле", предложный падеж слова "пол", дательный/предложный падежи слова "пола". Да еще добавлены несклоняемые слова "поло", "поль".

А вот если искать слово "полями", то будет:

поль, поля, полем, поле, полю, полями, полям, полях, полей

Поэтому для поиска именно слов типа "поле" в именительном падеже (в смысле - равнина, пшеничное поле) есть смысл искать его не в начальной форме (именительный падеж единственного числа), а в каком-нибудь падеже. Возможно, для этого стоит сделать функциональность сужения поиска путем задания нескольких падежей слова. Например, если искать в режиме НЕЧЕТКОГО поиска:

(поле и полями и полей)

то чтобы программа искала те и ТОЛЬКО те словоформы, которые одновременно соответствуют каждому из трех слов. Так слова "пол", "пола" и их формы, не относящиеся к указанным трем словам, будут исключены. Так можно существенно уточнить поиск, наделить его зачатками смысла. И легко обойтись без искусственного интеллекта.

Яндекс, Google, Yahoo!, вроде бы (на мой взгляд), у вас такого еще нет. Вы можете свободно использовать этот мой совет. С указанием моего авторства, естественно.

Попутно, Яндекс, а, может, вы, вместо своих турбо-страниц (это, за редким исключением, - излишняя и ненужная вещь), ВНОВЬ вернете "Оригинальные тексты"? А то ведь по мало-мальски частым запросам найти-то уже практически ничего невозможно. В выдаче присутствуют многие десятки клонов. Например, попробуйте САМИ рискнуть и потратить многие часы времени на поиск словосочетания "ремонт карбюратора". Ведь ваша система выдаст просто кучу страниц, дублирующих друг друга, зачастую, дословно. А полезной-то информации - или нету, или она где-то там, внизу выдачи, далеко. Раньше же, когда был сервис "Оригинальные тексты", такого не было все же или, если и было, то далеко не в том объеме, как сейчас (2025-2026 гг.).

Тут надо определиться, ЧТО именно вы хотите выдать пользователю. Если это - какой-нибудь "крутой" сайт, не взирая на полезность его контента, то это одно. Лично мне такие сайты не нужны совсем, их ценность имеет сильно-ОТРИЦАТЕЛЬНУЮ величину. А если именно ПОЛЕЗНЫЙ КОНТЕНТ - тут же обязательно необходимо учитывать авторство. Ведь не зря во всем мире принят институт права, в том числе, права авторства и права собственности. Это же не просто так, не только даже в угоду авторам или владельцам имущества. А ради отсеивания плагиаторов, чтобы не плодить мусорный контент. И чтобы полезный контент мог развиваться.

Общее время поиска снизилось где-то на 0,2-0,3 сек., составив 0,3-0,4 сек.

Версия 2.3

Однако, все еще осталось лимитирующее время на поиск имени файла и получение тех имен файлов, которые имеют индексы, содержащиеся в том или ином файле с именами 1.txt. Конечно, в предыдущей версии я определенно снизил это время. Но, оно все равно (было) высокое. Поэтому решил - поменять алгоритм поиска имен файлов.

Раньше я, для множества найденных индексов файлов, оценивал (в цикле) каждый индекс на предмет истинности/ложности логического выражения, состоящего из искомых слов. Истинно, когда слова входят (хотя бы один раз) в файл, имеющий такой индекс; причем, входят ТАК, что логическое выражение дает true. Ложно - в ином случае. Видимо, это длилось достаточно долго.

Поэтому я решил изменить алгоритм. Теперь для каждой формы (в случае НЕчеткого поиска) слова я нахожу соответствующие ему индексы. Т.е. - массивы индексов файлов, в которых это слово присутствует. Т.е. это слова типа "поле", "поля", "полем" и т.д. каждому из этих слов соответствует то или иное множество индексов.

А ПОТОМ я делаю объединение и нормализацию таких массивов. При этом дублирующие индексы исчезают.

Для того, чтобы упростить такие операции (точнее, их синтаксис), я написал функцию array_logical. Ну, чтобы каждый раз в программном коде не прописывать команды array_merge(). Итак, для каждого искомого ключевого слова формируется соответствующий ему массив индексов, с учетом словоформ этого слова. И так - для каждого искомого слова.

Например, ищется следующее логическое выражение:

слово1 И слово2 ИЛИ слово3

Или иначе:

слово1 && слово2 || слово3

Допустим, слово1, в том числе, его возможные словоформы, встречается в файлах сайта, соответствующих индексам 1, 2, 3, 6. Тогда как слово2 встречается в файлах сайта, соответствующих индексам 2, 8, 11.

А слово3 встречается в файлах сайта, соответствующих индексам 3, 9, 10. И мы хотим найти такие файлы сайта, в которых содержатся одновременно ОБА слова слово1, слово2, и/или же в них содержится слово3.

В итоге получится примерно такое логическое выражение:

array(1, 2, 3, 6) && array(2, 8, 11) || array(3, 9, 10)

Символы "&&" обозначают пересечение индексов, а символы "||" - объединение. Т.е. можно, конечно, реализовать соответствующую логику. Но, я пошел более наглядным, как мне кажется, путем: на базе функции eval. При помощи функции array_logical я делаю логические операции между массивами. Например, результатом указанного выше логического выражения будет:

array(2, 3, 9, 10)

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

Так вот, при таком подходе общее время нечеткого поиска снизилось еще сильнее и достигло примерно 0,2 секунды (для 1...2 тысяч файлов общим объемом примерно 30 МБ) при запросе от одного до 4...6 слов, в составе логического выражения. Это - в РНР 5.3. А если взять более новый РНР, например, 8.0, то там время поиска будет еще меньше. Все-таки, операции объединения/пересечения элементов массивов выполняются гораздо быстрее, чем когда для каждого индекса (в цикле) делать перебор и определять, соответствует ли он, этот индекс (точнее, файл, имеющий этот индекс), искомому логическому выражению или нет.

И, кроме того, программный код упростился.

Кстати, если объем файлов (и их число), увеличить гораздо более, скажем, на 1-2 порядка, до 100-300 тыс. файлов, то время поиска вырастет несильно. Потому что поиск будет, как и сейчас, осуществляться, в первую очередь, по каталогам файловой системы (сервера). Это - очень быстрые операции. При том, что число каталогов и файлов в каталоге metaphones вырастет несущественно. Едва ли некоторые файлы 1.txt накопят существенное количество строк. Почему? Да, потому, что число словоформ в любом языке, в том числе и в русском, не только конечно, но и достаточно ограниченно.

Ну, даже не знаю... едва ли возможно снизить время поиска еще дополнительно. Разве что, наиболее затратную по времени процедуру (поиск разных словоформ для каждого ключевого слова, программа keywords_FINDER_fuzzy.php) переписать на С/С++ и вызывать ее из РНР.

Как мне видится (могу ошибаться), получилась отличная процедура поиска вместо использования баз данных. Потому как выборка из баз данных даже при наличии индексации делается медленнее, даже на достаточно мощном сервере. Который мощнее моего компьютера, как минимум, на порядок, а то и больше. При том, что эта моя процедура будет работать не намного медленнее при существенном увеличении числа файлов. Даже для большого общего объема файлов, в которых производится поиск. По моим оценкам, программа будет работать вполне уверенно при числе индексированных файлов, как минимум, до 200-500 тысяч даже на компьютере средней мощности (по нынешним меркам). При достаточно большом числе файлов может возникнуть проблема с массивами. Возможно, придется делать отдельную логику для работы в массивами по частям. Но, пока у меня такой задачи нет.

Вот только индексация длится достаточно медленно даже для указанного числа файлов. Например, если число файлов будет составлять 20 тысяч, их общий объем - 300 МБ, то индексация на моем компьютере займет примерно день. А время поиска будет, вероятно, примерно таким же.

Объем файлов - имеется в виду, в основном, только чистый их контент, безо всяких шаблонов (типа тех, что дает какой-нибудь Vue или React).

Впрочем, на сервере ее можно периодически запускать ночами (индексировать по частям).

Вот она, версия 2.3.

С уважением, Салимоненко Д.А.