GotAI.NET

Форум: Проблемы искусственного интеллекта

 

Регистрация | Вход

 Все темы | Новая тема Стр.1 (2)След. > >>   Поиск:  
 Автор Тема: Алгоритмы поиска слова
Corwin
Сообщений: 1324
Алгоритмы поиска слова
Добавлено: 07 авг 07 4:06
Предлагаю обсудить различные алгоритмы поиска слова (строгие и нестрогие) в базе данных. Такой поиск может быть необходим для нахождения индекса слова в базе данных и соответственно должен проходить достаточно быстро.
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Поиск слова
Добавлено: 07 авг 07 4:07
Всего мной на практике было реализовано и испытанно три разных алгоритма поиска слов (линк на саму программу для испытаний алгоритмов находиться ниже) :
Прямой поиск,
Поиск по дереву,
Интеллектуальный поиск;
Прямой поиск реализирован простым сравнением искомого слова со словами в базе данных.
Поиск по дереву: слово в базе данных представляется в форме дерева состоящего из букв. Соответственно такой поиск хорошо подходит если нужно найти точную копию слова или его части.
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Поиск слова
Добавлено: 07 авг 07 4:08
Интеллектуальный поиск. Сама идея возникла на основании следующего текста (который в большинстве случаев приводиться как анекдот ) :

«По рзелульаттам илссеовадний одонго анлигйсокго унвиертисета, не иеемт занчнеия, вкокам пряокде рсапожолена бкувы в солве. Галвоне, чотбы преавя и пслоендяя бквуы блыи на мсете. Осатьлыне бкувы мгоут селдовтаь в плоонм бсепордяке, все-рвано ткест чтаитсея без побрелм.»

Собственно появилась идея, что поиск слова человеком, основывается на первой и последней букве, а также вхождения остальных (центральных) букв в произвольном порядке. Ну и конечно на субъективном ощущении длины слова.
Итак, реализованный алгоритм интеллектуального поиска состоит из следующих стадий:
1. Нахождение слов из БД в которые "вошли" символы искомого слова и выражение этого значения в процентном виде. Порядок вхождения символов роли не играет. Например при поиске слова "бсаоак" в БД найдется слово "собака". При поиске "бсаоа" тоже найдется слово "собака" но уже с достоверностью в 78% (просто не все символы были найдены)
2. Проверка соответствия первого и последнего символа в искомом слове и найденном слове из БД. К примеру "бсаоак" уже не будет распознаваться как "собака" зато "сбокаа" найдется в БД как "собака", что собственно имеет много общего с приведенным выше примером быстрого чтения текста человеком
3. Скорее просто дополнительный этап для того чтобы найти параметр связанности символов в найденном слове. "связанности" - это чтобы порядок символов в найденном слове соответствовал порядку символов в искомому слову. Выражается также в процентном соотношении. Возвращаясь к примеру с "собакой": при поиске "собака" связанность будет равна 100%, при "собка" - 67%, а при "бсаоак" - 33%.
Собственно интеллектуальный поиск хорошо подходит не только для строго поиска слова но также и для не строгого (собственно из рассмотренных алгоритмов на это способен только он) т.е. Для поиска части слова, для поиска слова с очепяткой, с разрывом (лишбними символами), слоа с пропажей символов, также хорошо подходит для проверки орфографии или для поиска слова распознанного системой ОРС (оптического распознания символов) где есть массив символов причем некоторые символы могут заменяться другими (при неточности распознавания).
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Поиск слова
Добавлено: 07 авг 07 4:08
Немного о самой программе.
Скачать можно по адресу http://filesexchange.narod.ru/WordFinder.rar Размер 33 кб: Для работы программы нужен Фреймворк 2.
Наперед извиняюсь за интерфейс и возможные ошибки Ведь целю написания программы был не готовый программный продукт, а проверка теорий.
В главном окне программы находится окно ввода слова (вверху), окно вывода результатов (под окном ввода слова), окно обучения (посредине) и панель настройки (справа).
На панели настройки можно выбрать тип поиска: прямой поиск (Find Word), Поиск по дереву (Search by tree), Интеллектуальный поиск (Intelligent search) и несколько параметров для интеллектуального поиска.
Для поиска сначала нужно "обучить" программу выборке слов. Т.е. внести слова в базу данных. Для этого нужно скопировать текст в окно обучения (в тексте слова должны быть выделены абзацами, т.е. каждое слово в отдельном рядке) и нажать кнопку Learn (для прямого поиска нажимать эту кнопку не обязательно). Если выборка большая, то обучение может занять некоторое время. Повторное нажатие этой кнопки приведет к добавлению слов в БД.
Дальше вводим слово в окошко вверху и жмем Find. Если слово нашлось то выведется его индекс. При интеллектуальном поиске также выведется что за слово нашлось. Также в этом окне показывается сколько было затрачено времени на поиск (в миллисекундах).

Немного о параметрах интеллектуального поиска:
Filter: Used chars - Количество (в процентах) совпавших букв в слове из БД. По значению в поле будет проводиться отфильтровка. Т.е. при значении 100% будут учитываться только слова, буквы которых полностью совпали (порядок букв значения не имеет). При подсчете значения учитывается также отличие в длине слова.
Check first and last char - Проверка первого и последнего символа в слове из БД с искомым словом.
Check union - проверка связанности символов слова
Filter: unions - минимальный порог связанности для принятия слова.
Show Info - Отображать инфо про сравнение слов. Для использования этого параметра рекомендуется использовать небольшую БД. Также рекомендуется установить поля Filter: Used chars и Filter: unions в -1 и выключить сравнение первого и последнего символа.

В программе стоит ограничение в 2000 слов и некоторые лимиты для построения дерева. Так что не пытайтесь засунуть в нее слов сверх нормы.
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Поиск слова
Добавлено: 07 авг 07 4:09
Результаты.

По умолчанию в окне обучения находится выше приведенный текст с перепутанными буквами. Жмем Learn и можем испытать работу алгоритмов на этом тексте.
К примеру при интеллектуальном поиске слова «буквы» вот что нашлось:

Word Index: 13
Finded word: б к у в ы
Word Index: 21
Finded word: б к в у ы
Word Index: 26
Finded word: б к у в ы

(между буквами пробелы для более удобного чтения)

В архиве с программой также находиться файл (WordsArray.txt) в котором находиться 1419 слов. Обучаем программу этим словам и тестируем алгоритмы на скорость. Получилось следующее:
Слово «человек»:
Найдено 3 слова.
Прямой поиск: 297 миллисекунд
Поиск по дереву: 0 миллисекунд
Интеллектуальный поиск: 15 миллисекунд

Слово «информационного»:
Найдено 7 слов.
Прямой поиск: 297 миллисекунд
Поиск по дереву: 7 миллисекунд (точно замерить не удалось)
Интеллектуальный поиск: 55 миллисекунд

Да, результаты не очень. В смысле данные времени работы слишком малы для анализа. Тестировалось на Pentium Core2Duo 2400 Mhz
Буду благодарен, если напишите какое у Вас время поиска этих слов.

Но уже можно выделить что наилучший алгоритм поиска слов это поиск по дереву. Дальше следует интеллектуальный поиск и прямой поиск. Впрочем, не стоит забывать что интеллектуальный поиск по своим возможностям намного превосходит поиск по дереву.
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Поиск слова
Добавлено: 07 авг 07 4:11
Примечания:
Второй и третий способ были реализованы на платформе моей модельки ИИ, поэтому исходники выложить не могу. Собственно сама модель разрабатывалась для других целей, но как видим очень даже не плохо справляется с поставленной задачей поиска слов. Такой себе побочный эффект. Поскольку части алгоритмов дописывались поверх существующей платформы (у которой первоначальные цели были несколько другими) то алгоритмы получились несколько тормозными из-за использования кучи лишних операций, и думаю, что если написать аналогичные специализированные алгоритмы рассчитанные только на поиск слов, то можно получить прирост производительности где-то в 2-3 раза больше (более быстрое нахождение слова).

Поскольку для двух последних алгоритма необходима предварительно сформированная БД, то они не подходят для поиска слова во внешних файлах (формирование файла в нужную структуру довольно продолжительная операция). Исключения могут составить только случаи когда нужно часто искать слова в конкретных файлах. Тогда такие файлы можно просто закэшировать в нужном формате.
[Ответ][Цитата]
Плюмаж
Сообщений: 110
На: Поиск слова
Добавлено: 07 авг 07 4:55
Под базой данных имеется в виду множество отдельных слов? Или множество текстов? (под текстом здесь понимается последовательность слов).

Какие критерии Вы полагаете использовать для сравнения алгоритмов? Например:

1. По времени - "который быстрее тот лучше" - не годится. Самый быстрый алгоритм, здесь, это тот, который просто, не проверяя, выдает "0 слов найдено"
2. По количеству найденных слов – не годится
[Ответ][Цитата]
Плюмаж
Сообщений: 110
На: Поиск слова
Добавлено: 07 авг 07 9:26
От каждого – по алгоритму!

Сначала, картинка.
http://rundschau.narod.ru/FindWord.JPG (102 кб)

Рисунок 1. Мы рассматриваем буквы (некая неделимая сущность). Последовательность букв образует текст.

Рисунок 2. Вводим понятие расстояния от буквы к букве.

Рисунок 3. Буквы в тексте могут образовывать связи. Каждая связь характеризуется парой букв и расстоянием между ними в данном тексте.

Рисунок 4. Дана некоторая связь АВ(2). Дан некоторый текст, содержащий букву «А». Если бы в этом тексте могли образовываться собственные связи АВ, с различными расстояниями, то они полностью (т.е. со степенью соответствия равной 1) соответствовали-бы связи-образцу если расстояния в связях совпадали. (гистограмма ниже).

Рисунок 5. В одном тексте (слово «_TWO_») может быть множество связей.

Рисунок 6. Сравнение двух текстов на соответствие друг-другу – если мы можем сравнивать две связи на степень соответствия (эквивалентности) друг-другу, то можем и
сравнивать степень соответствия текстов. На данном рисунке, условно показано, что такой степенью соответствия может быть отношение площади пересечения множеств связей, существующих в обоих текстах, к площади множеств связей, существующих хотя-бы в одном из двух сравниваемых текстов.

Последний рисунок. Правила соответствия связей друг-другу.

Посмотрим, что получаем. Будем говорить, что если степень соответствия текстов больше нуля, но меньше единицы, то тексты «подобны» (чем больше степень соответствия, тем более подобны тексты). Если степень соответствия равна единице, то тексты идентичны.

Поиск слова в текстах – отбор из множества текстов (БД) таких, степень соответствия которых тексту-образцу больше нуля.

Рассмотрим примеры текстов, которые будут подобны слову «РОЗА».
«РОЗА» (идентичны)
«БЕЛАЯ РОЗА»
«123-Р-4-О-5-З-6-А-»
«МИМОЗА»
«АСТРА» (слабоподобны)
«АЗОР» (идентичны, только если нет символов «начало текста» и(или) «конец текста». Если-же такие символы есть, то - тексты подобны, но не идентичны)
«РЗА»
«РРРОООЗЗЗЗААА»
«Р-КПСС-ОЗА»

Ну, и т.д.


Вотъ.
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Поиск слова
Добавлено: 07 авг 07 21:48
>Под базой данных имеется в виду множество отдельных слов? Или множество текстов? (под текстом здесь понимается последовательность слов).

В первоначальной идее имелось в виду множество отдельных (уникальных) слов. Но поскольку алгоритмы написаны на уже существующей платформе то получился вариант поиска по тексту (последовательности слов). Впрочем одно второму не мешает

>По времени - "который быстрее тот лучше" - не годится. Самый быстрый алгоритм, здесь, это тот, который просто, не проверяя, выдает "0 слов найдено"

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

Предложенный вами алгоритм немного похож на проверку связанности которая используется в моем алгоритме интеллектуального поиска. Правда там я смотрю только на связи между соседними буквами (количествоСвязей = ДлинаСлова-1), а Вы предлагаете учитывать связи всех используемых букв в слове (количествоСвязей = Факториал(ДлинаСлова-1)). Если еще и в БД искать все возможные связи, то это будет довольно тормозно...
Впрочем, Вы будете пробовать реализовать этот алгоритм на практике?
[Ответ][Цитата]
Плюмаж
Сообщений: 110
На: Поиск слова
Добавлено: 08 авг 07 1:16
Corwin
> Показатель скорости работы алгоритма - не такой уже и плохой показатель

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

> ...Вы предлагаете учитывать связи всех используемых букв в слове...

Разумеется, это не обязательно. Просто, идеальный случай.

> Если еще и в БД искать все возможные связи, то это будет довольно тормозно...

Очень и очень, я бы сказал. Например, одним из элементов БД может быть "Война и мир", или полное собрание сочинений Ленина.

> Впрочем, Вы будете пробовать реализовать этот алгоритм на практике?

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

Алгоритм А. Нашел B cлов за C секунд
Алгоритм D. Нашел E cлов за F секунд
Алгоритм G. Нашел H cлов за I секунд

Какой из них лучше? Заметьте, что алгоритм А реализован на языке программирования X, алгоритм D - на Y, а G - на Z.
[Ответ][Цитата]
daner
Сообщений: 4593
На: Поиск слова
Добавлено: 08 авг 07 2:33
Цитата:

> Показатель скорости работы алгоритма - не такой уже и плохой показатель

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

Плюмаж, ну не знаете вы основ информатики, ну зачем же тогда спорить.
Алгоритм в 99% случаев оценивается по 2 основным фактором: (1) скорость (2) память
И тот и другой из способов, оценивается экспериментально, только если не получается оценить аналитически. Обычно алгоритмы поиска аналитически оцениваются нормально.
Хотите знать подробнее читайте литературу, перед тем как спорить
Теория сложности вычислений
[Ответ][Цитата]
Плюмаж
Сообщений: 110
На: Поиск слова
Добавлено: 08 авг 07 2:51
daner

Самый быстрый алгоритм поиска слова:


Print "0 слов найдено"


Расход памяти, заметьте, минимальный.
[Ответ][Цитата]
Плюмаж
Сообщений: 110
На: Поиск слова
Добавлено: 08 авг 07 3:05
daner

Еще чуточку спора - из любви с исскуству.

Есть два алгоритма, отработали одинаково по времени. Один вернул два слова, другой - три. Какой из них лучше? Далее, допустим, искали слово "собака", то присутствие в результатах слова "абракадабра" допустимо? Ну и т.д.

Увы, серые мы ...
[Ответ][Цитата]
Плюмаж
Сообщений: 110
На: Поиск слова
Добавлено: 08 авг 07 11:46
Итак...
http://rundschau.narod.ru/FindWordV1.rar (185 кб)

Использован символ "начало текста".
Тексты при сравнении регистрочувствительны («человек» и «Человек» - это не идентичные тексты, но высокоподобные).

f( |N-M| ) = f(X) = 1/(X+1)


Результат загрузки Вашей БД, Corwin:

Количество текстов: 1418
Общее количество связей: 60232
Связей, в среднем на один текст: 42,4767


Тесты (степень подобия показана в процентах):


-------------------------------------------------------------
Начат поиск:
буквы.......... 15 cвязей
Ничего не найдено подобного не менее, чем на 50%

Поиск завершен. Затрачено времени 63.0000000 мс.
В среднем на каждый текст в БД затрачено 0.0444288 мс
-------------------------------------------------------------

Начат поиск:
буквы.......... 15 cвязей
--------------------------------------------------
Текст Подобие
--------------------------------------------------
вкусы________________________________________27.66
вкусы________________________________________27.66
субъекты_____________________________________11.68
будем________________________________________11.11

Поиск завершен. Затрачено времени 77.0000000 мс.
В среднем на каждый текст в БД затрачено 0.0543018 мс
Начат поиск:
человек.......... 28 cвязей
--------------------------------------------------
Текст Подобие
--------------------------------------------------
человек_____________________________________100.00
человек_____________________________________100.00
человека_____________________________________77.78
человека_____________________________________77.78
человека_____________________________________77.78
человека_____________________________________77.78
человека_____________________________________77.78
человека_____________________________________77.78
человеку_____________________________________77.78
человека_____________________________________77.78
человека_____________________________________77.78
Человек______________________________________60.00

Поиск завершен. Затрачено времени 140.0000000 мс.
В среднем на каждый текст в БД затрачено 0.0987306 мс
-------------------------------------------------------------

Начат поиск:
информационного.......... 120 cвязей
--------------------------------------------------
Текст Подобие
--------------------------------------------------
информационного_____________________________100.00
информационного_____________________________100.00
информационного_____________________________100.00
информационного_____________________________100.00
информационного_____________________________100.00
информационного_____________________________100.00
информационного_____________________________100.00
информационной_______________________________74.87
информационной_______________________________74.87
информационной_______________________________74.87
информационной_______________________________74.87
информационной_______________________________74.87
информационное_______________________________74.87
информационное_______________________________74.87
информационной_______________________________74.87
информационных_______________________________62.89
информационных_______________________________62.89
информационных_______________________________62.89
информационные_______________________________62.89
информационных_______________________________62.89
информационные_______________________________62.89
информационных_______________________________62.89
информационных_______________________________62.89
информационными______________________________57.41
информационными______________________________57.41
информации___________________________________53.80
информации___________________________________53.80
информации___________________________________53.80
информации___________________________________53.80

Поиск завершен. Затрачено времени 594.0000000 мс.
В среднем на каждый текст в БД затрачено 0.4188999 мс
-------------------------------------------------------------

Начат поиск:
фактор.......... 21 cвязей
--------------------------------------------------
Текст Подобие
--------------------------------------------------
факторами____________________________________46.67
факта________________________________________38.46
дефакто______________________________________31.25

Поиск завершен. Затрачено времени 109.0000000 мс.
В среднем на каждый текст в БД затрачено 0.0768688 мс
-------------------------------------------------------------


Вотъ.

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

Примечание: т.к. некоторые тексты повторяются в Вашей БД (например "человек"), то в резлуьтатах эти тексты тоже выводятся, хоть они и одинаковые (например, в результатах поиска "человек" видно это).

Также, тест с поиском "буквы" повторен дважды - второй раз снижен порог подобия для включения текста в ответ.
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Поиск слова
Добавлено: 08 авг 07 17:32
Результаты впечетлили… Только проверить программу не удалось. Пишет что битый архив
[Ответ][Цитата]
 Стр.1 (2): [1]  2След. > >>