Быстрый поиск слова по маске.

← →
Дмитрий С © (2011-06-15 12:15) [0]

Есть список слов WordList (порядка 100000 слов)

Необходимо достать любое слово (с равномерным распределением) из WordList удовлетворяющее условиям:
- Соответствие маске Mask, например, ?д??? - т.е. 5 букв, вторая "д".
- Слово не входит в список исключений ExcludeList.

Сделать это нужно максимально быстро используя кеши, индексы, вобщем память не жалеть.

Какие предложения?

← →
oldman © (2011-06-15 12:24) [1]

Составить еще n+1 список (n=максимальное количество букв в словах списка)

1 список - первые буквы слов
2. список - вторые буквы
...
n список - n-е буквы

n+1 список - количество букв в слове

ну и n+1 индекс

:)))

← →
oldman © (2011-06-15 12:27) [2]

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

4м
4а
4м
4а

Для маски "??м?" в третьем списке по индексу ищем "4м"
Найдет, думаю, быстро

← →
Игорь Шевченко © (2011-06-15 12:33) [3]

> Какие предложения?

линейный поиск

← →
Дмитрий С © (2011-06-15 12:41) [4]

> линейный поиск

Слишком медленный получается. Всяко хочется ускорить

> oldman © (15.06.11 12:27) [2]

Хорошая идея, ее надо обдумать. Например, еще про маски с двумя, тремя буквами ?а?б?в?

← →
TUser © (2011-06-15 12:45) [5]

А в масках - только вопросы?

← →
Дмитрий С © (2011-06-15 12:46) [6]

> TUser © (15.06.11 12:45) [5]

Да, один вопрос - одна буква. Звездочек нет.

← →
QAZ (2011-06-15 12:46) [7]

а какой смысл в таком бессмысленом поиске и что делать например с *в*о* ?

← →
Думкин © (2011-06-15 12:55) [8]

Дерево, например.

??д???

Первый уровень - каждая ветка - буква. В ветке слова содержащие эту букву.

Идем к ветке в которой слова с буквой "д". В ней ветки - числа. Число - номер в слове, где эта буква встречается. Идем к числу 3.

??д??в?

--
тут варианты. Можно начало как и в первой ситуации, а потом уже идти на третий уровень по букве "в" и потом к числу 6.
=================

Т.к. памяти у нас вагон. то проблем никаких. :)

← →
TUser © (2011-06-15 13:02) [9]

Можно использовать алгоритм Ахо-Корасика, будет быстрее, чем просто [8].

Но если в запросах встречается так много вопросов, то не факт, что это оптимально, перебор уж больно большой. Я бы, наверное, в каждом слове посчитатал буквы и сотворил дерево типа
Root -> ( слова, в которых не менее 5 букв а -> ( не менее 5 букв б ровно 4 буквы б ... ) слова, в которых ровно 4 буквы а -> ... слова, в которых ровно 3 буквы а -> ... ... )

← →
oldman © (2011-06-15 13:12) [10]

А что, БД на 100000 записей при большом количестве памяти банальный locate так уж долго выполняет?
В условии "достать любое слово", значит, если поиск успешен - задача решена.

← →
RWolf © (2011-06-15 13:29) [11]

раз уж память мы не жалеем :) вот алгоритм — быстрее некуда. правда, требует некоторой подготовки данных, и использовать его будет реально только на не слишком длинных словах.
пусть N- максимальная длина слова.
нумеруем все слова.
подготавливаем N-мерный массив указателей, по 32 элемента на измерение (т.е. буквы алфавита, Ё выкидываем для ровного счёта).
заполняем его указателями на списки номеров слов, генерим сами списки (это самый долгий этап).
поиск слов, соответствующих маске ??а?н?, сведётся к взятию элемента массива с координатами (?, ?, "а", ?, "н", ?), где "?" - любой индекс.

← →
Кщд (2011-06-15 13:33) [12]

Трехмерный массив:
X - символы(или, напр., коды символов),
Y - позиция в слове,
Z - слова из WordList(индексы в массиве), которых нет в ExcludeList.

Пример.
Дано: имеется маска "?а?б?".

Поиск:
1. Ищем все слова(по оси Z), для которых (x,y) = ("a", 2);
2. ищем непустые вхождения в массив по индексу (x,y) = ("б", 4).

← →
RWolf © (2011-06-15 13:33) [13]

поправочка: "?" — это отдельный 33-й элемент, означающий "любая буква".

← →
Кщд (2011-06-15 13:40) [14]

RWolf © (15.06.11 13:29) [11]
например, пусть самое длинное слово - "человеконенавистничество", т.о. кол-во элементов массива - 32^24.

"заполняем его указателями на списки номеров слов" - это что?

← →
RWolf © (2011-06-15 13:42) [15]

> т.о. кол-во элементов массива - 32^24.

вот именно :)

> "заполняем его указателями на списки номеров слов" - это
> что?

mas("к","р","?","?") → "краб" → "кран" → "крот" → …

← →
MBo © (2011-06-15 13:47) [16]

Ternary search tree (TST) подходят для поиска в словаре с использованием wildcard

Также можно посмотреть, есть ли возможность такого поиска в Trie (для которых реализацию найти проще)

← →
sniknik © (2011-06-15 14:24) [17]

> Слишком медленный получается. Всяко хочется ускорить
уточни, это вообще (с чего решил?), или именно у тебя получается медленно?

> Какие предложения?
не париться...
держать все 100тыс в банальном датасет-е (в памяти), и фильтровать при нужде.

← →
Sha © (2011-06-15 14:28) [18]

Составляем кроссворды?

← →
Думкин © (2011-06-15 14:30) [19]

> Sha © (15.06.11 14:28) [18]
>
> Составляем кроссворды?

Я подобное делал для "Эрудита".

← →
Дмитрий С © (2011-06-15 14:36) [20]

> Составляем кроссворды?

так точно.

> держать все 100тыс в банальном датасет-е (в памяти), и фильтровать
> при нужде.

фильтр как раз получается медленным.

Я уже и так его избавил от выделений/освобождений памяти. Добавил кеш: для каждой маски сохраняется список слов (указатели на них). Получил из 22000 запросов к списку слов - 20000 - попаданий в кеш - уже хороший показатель. Количество самих запросов я пока не могу сократить.
Картину портит только наличие слов исключений - пока что исключаю их с помощью двухуровнего перебора - хотя можно быстрее - т.к. оба списка отсортированы.

> MBo © (15.06.11 13:47) [16]

Спасибо, буду читать... и улучшать английский походу :)

← →
Дмитрий С © (2011-06-15 14:38) [21]

> кол-во элементов массива - 32^24.

Да уже 32^9 за рамках 32битной оперативы. да и любого на данный момент винта:)

Помню рекламу какой-то газеты, мол они составляют кроссворды вручную, а не с помощью бездушных машин, которые штампуют их по сто тыщ в минуту:) Хотел бы я посмотреть на эту машину бездушную :)

← →
Sha © (2011-06-15 14:40) [22]

> Дмитрий С © (15.06.11 14:36) [20]

Исключать надо до, а не в процессе.

← →
Дмитрий С © (2011-06-15 14:43) [23]

> Исключать надо до, а не в процессе.

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

← →
Sha © (2011-06-15 14:45) [24]

> Дмитрий С © (15.06.11 14:38) [21]
> Да уже 32^9 за рамках 32битной оперативы

Слова разной длины должны быть в разных списках/кешах/таблицах и т.п.
И сразу все прекрасно влезет.

← →
Дмитрий С © (2011-06-15 14:48) [25]

> Sha © (15.06.11 14:28) [18]
>
> Составляем кроссворды?

Всё никак гениальная мысль не посетит

← →
MBo © (2011-06-15 14:59) [26]

http://stackoverflow.com/questions/1953080/good-algorithm-and-data-structure-for-looking-up-words-with-missing-letters

← →
oldman © (2011-06-15 15:09) [27]

> Дмитрий С © (15.06.11 14:36) [20]
>
> > Составляем кроссворды?
>
> так точно.

Делай линейный поиск и не парься. Часик можно и подождать.

← →
Sha © (2011-06-15 15:24) [28]

> oldman © (15.06.11 15:09) [27]
> Делай линейный поиск и не парься. Часик можно и подождать.

Не дождется.
Нужен свой хеш для каждой маски.

> Ему нужно еще равномерную случайность )
>

На самом деле неравномерную, но это я уже сделал :)

> MBo © (15.06.11 14:59) [26]
> http://stackoverflow.com/questions/1953080/good-algorithm-
> and-data-structure-for-looking-up-words-with-missing-letters

Я пока плохо дружу с английским, но насколько я понял, там для каждого слова из словаря изначально составляются всевозможные маски. Затем для каждой маски подсчитывается некий hash и записывается в индекс.
А при поиске по маске находится строка в индексе и уже линейно находятся подходящие слова. Все правильно?

> Sha © (15.06.11 15:51) [30]

использованное удаляем
в следующем поиске найдется следующее
все по порядку - равномерная случайность?

> Дмитрий С © (15.06.11 14:38) [21]
> Хотел бы я посмотреть на эту машину бездушную :)

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

> oldman © (15.06.11 16:55) [32]
> использованное удаляем
> в следующем поиске найдется следующее
> все по порядку - равномерная случайность?

Нет.
Вот, например, в кроссворде требуется одно единственное слово ?а?а.
Надо, чтобы попытке составить этот кроссворд шансы у слов мама и папа
были примерно равны.

Сейчас 100 из 120 секунд работы алгоритма тратится на выполнение строки
AnsiCompareStr(Excludes[Iex], WorkingArray^[I].Word) блин.

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

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

> Sha © (15.06.11 17:07) [33]
> Надо, чтобы попытке составить этот кроссворд шансы у слов
> мама и папа были примерно равны.

тогда фильтр по шаблону и random

> oldman © (15.06.11 17:22) [35]
> тогда фильтр по шаблону и random

Зачем фильтр?
По [33] у нас есть 32*32 списков для типа маски ?X?X.
Берем из них список для маски ?а?а.
Количество элементов известно.
Далее Random.

> Сейчас 100 из 120 секунд работы алгоритма тратится на выполнение
> строкиAnsiCompareStr(Excludes[Iex], WorkingArray^[I].Word)
> блин.

ну так надо сравнивать не строки, а их хэши.

> Дмитрий С © (15.06.11 17:18) [34]
> Получается нереально много вариантов

Должно быть меньше.
Скорее всего, ты что-то делал не так, как написано в [33].

> Дмитрий С © (15.06.11 17:18) [34]
> Сейчас 100 из 120 секунд работы алгоритма тратится на выполнение
> строки AnsiCompareStr(Excludes[Iex], WorkingArray^[I].Word) блин.

На самом деле вообще не надо сравнивать.
Список слов есть.
Флаги проходили?

> AnsiCompareStr(Excludes[Iex], WorkingArray^[I].Word)

В данном случае сравнение идет уже со списком слов-исключений. Т.е. уже после фильтрации по основному словарю. Получается, что на фильтрацию тратится в 7 раз меньше времени чем на исключение слов :(

> Должно быть меньше.
> Скорее всего, ты что-то делал не так, как написано в [33].

Возможно. Но посчитаем.
Пусть в кроссворде 50 слов и у каждого 2-3 пересечения.
Я делал так:
1. Ищем возможные буквы, которые могут быть в пересечениях - просто перебираем слова по-вертикали и по-горизонтали для выбранного перекрестка и смотрим возможные буквы. Этот пункт не дает преимуществ, т.к. слов столько, что на перекрестках возможны почти все буквы (очень редко когда меньше 30) - т.е. смысла нет.
2. Далее составляем список возможного первого слова - обычно около 19000 вариантов.
3. Затем для пересекающего его слова находим список слов - обычно около 500.
4. Затем уже для второго слова ищем пересекающееся слова (т.е. пункт 3, только не для первого слова, а для второго) - их тоже обычно около 500.
И их так и будет по 500, пока не получится хотя бы один цикл. Теперь посчитаем количество вариантов, если цикл не наступит через 5 слов, получаем 19000 * 500^4 = 1"187"500"000"000"000 вариантов - это уже нереально перебрать, а отсутствие цикла в 5 слов - дело обычно для кроссворда.

Я, конечно, не мастер объяснять, но надеюсь вы меня поняли.

Быстрый поиск слова по маске. Найти похожие ветки