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

← →
Дмитрий С © (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]
> Делай линейный поиск и не парься. Часик можно и подождать.

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

← →
oldman © (2011-06-15 15:31) [29]

> Sha © (15.06.11 15:24) [28]

Ну так на 100000 записей можно и locate, о чем я уже докладывал
:)

← →
Sha © (2011-06-15 15:51) [30]

> oldman © (15.06.11 15:31) [29]

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

← →
Дмитрий С © (2011-06-15 16:55) [31]

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

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

> 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 и записывается в индекс.
А при поиске по маске находится строка в индексе и уже линейно находятся подходящие слова. Все правильно?

← →
oldman © (2011-06-15 16:55) [32]

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

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

← →
Sha © (2011-06-15 17:07) [33]

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

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

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

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

← →
Дмитрий С © (2011-06-15 17:18) [34]

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

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

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

← →
oldman © (2011-06-15 17:22) [35]

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

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

← →
Sha © (2011-06-15 17:30) [36]

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

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

← →
RWolf © (2011-06-15 17:31) [37]

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

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

← →
Sha © (2011-06-15 17:35) [38]

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

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

← →
Sha © (2011-06-15 17:38) [39]

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

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

← →
Дмитрий С © (2011-06-15 17:51) [40]

> 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 слов - дело обычно для кроссворда.

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

← →
Sha © (2011-06-15 17:58) [41]

> Дмитрий С © (15.06.11 17:51) [40]

Список слов-исключений виртуальный. Его нигде нет.
Это просто пометки у использованных слов основного словаря.

Перебор с откатами - совсем не то же самое, что составление списков в твоем алгоритме.

← →
Дмитрий С © (2011-06-15 18:07) [42]

> Перебор с откатами - совсем не то же самое, что составление
> списков в твоем алгоритме.

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

> Это просто пометки у использованных слов основного словаря.

После фильтра всей базы слов по маске, я делаю всего-лишь один проход по результату, чтобы также исключить слова-исключения. Т.е. Итераций цикла = количество в результате слов + (не *) количество слов-исключений, т.е. как бы дополнительный цикл, и все работает быстро, кроме этой AnsiCompareStr()

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

как реализован фильтр базы слов по маске?

← →
Sha © (2011-06-16 01:34) [44]

> Дмитрий С © (15.06.11 17:51) [40]

Твой подсчет не соответствует алгоритму [33]. Ты считаешь слова, а надо считать списки.
С каждым новым пересечением их число увеличивается не более чем в 32 раза.
Фактически мы ищем маски, а не слова, мама это будет или папа, нам все равно.
Нам нужно только, чтобы в списке было хотя бы одно слово.
Это основа, которую можно оптимизировать.

> фильтра всей базы слов по маске

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

← →
Sha © (2011-06-16 08:18) [45]

> Sha © (16.06.11 01:34) [44]
> Нам нужно только, чтобы в списке было хотя бы одно слово.

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

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

← →
Sha © (2011-06-16 08:30) [46]

> Sha © (16.06.11 08:18) [45]
> из соответствующего списка.

или списков (если слово соответствует нескольким типам масок).

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

← →
VirEx © (2011-06-16 13:00) [47]

>Дмитрий С © (15.06.11 12:15) [0]

разбить циклы поиска на несколько потоков, и экспериментально подобрать их оптимальное количество

← →
VirEx © (2011-06-16 13:53) [48]

иллюстрация: http://zalil.ru/31273236

и небольшое описание:
каждый поток берет определенный "блок" из списка слов (например с 0 до 500) для проверки соответствия слова с маской

в цикле проверяется соответсвующий символ, и с каждым разом (чем меньше "?" в маске) цикл уменьшается в разы

результат соответствия маски-слова можно сохранить как "в слове" так и в "маске" (желательно конечно сохранять список (хешей) масок в каждом слове)

в итоге накапливается множество соответствий "слово-хэш" и поиск ускоряется в разы

← →
VirEx © (2011-06-16 14:03) [49]

> в итоге накапливается множество соответствий "слово-хэш"
> и поиск ускоряется в разы

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

← →
Дмитрий С © (2011-06-16 18:06) [50]

> VirEx © (16.06.11 13:00) [47]

У меня сейчас реализовано также, только наоборот. Простым перебором находится список слов подходящих по маске и сохраняется.
Т.е. имею ассоциированный массив
маска1=>список слов
маска2=>список слов
....
И если запрос повторяется (т.е. поиск по маске, которая уже была) - ответ на запрос возвращается из сохраненного списка. На практике получилось более 90% попаданий в кеш, при этом используется всего около 300МБ ОЗУ. (это около 200 попыток составить кроссворд из 50 слов).

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

Еще раз повторюсь, что 100 секунд из 120 сейчас теряется на исключение "слов-исключений", а точнее на выполнение функции AnsiCompareStr - что в ней такого долгого - хз (

> Sha ©

Т.е. грубо говоря надо учитывать не списки слов, а список возможных букв в перекрестке, так?
Например, в первом перекрестке (слов 1 и 2) изначально возможны 32 буквы, берем первую, затем по списку слов определяем возможные буквы в остальных перекреточных клетках этих самых слов 1 и 2. Затем берем первую букву на втором перекрестке и так далее продолжаем, пока на всех перекрестках не возьмем по букве, ну и останется только подобрать слова под перекресточные буквы.

← →
Sha © (2011-06-16 20:08) [51]

> Дмитрий С © (16.06.11 18:06) [50]

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

Принципиальный момент здесь состоит в том, что мы не заполняем кроссворд словами.
Мы заполняем его масками.

На подготовительном этапе мы склеиваем слова мама и папа в маску ?а?а,
слова сила и пила в маску ?и?а,
а обе эти маски храним в списке масок типа ?@?@.

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

На финише мы вместо найденных масок подставляем слова, если сможем.

← →
Дмитрий С © (2011-07-15 18:49) [52]

В общем долгими экспериментами установил, что, например такой ужасный шаблон http://ssu.argi.ru/cross.png заполняется любым способом (перебор, монтекарло) крайне долго: единственный результат удалось получить примерно за час работы.
Скаченные мной програмки для составления кроссвордов не позволяли задать шаблон такого размера, поэтому убедиться в существовании действительно быстрого алгоритма мне не удалось.

Дальнейшие поиски в сети дали свой результат - появилась новая идея - использовать Генетический алгоритм. Почитав википедию, решил потратить день на реализацию.

В качестве существ выбрал набор букв в перекрестках. Т.е. одно существо - это полный набор букв в перекрестках. Если существо жизнеспособно (т.е. найден подходящий набор букв), то составить кроссворд не составит труда и времени.
Рассмотрим этапы.
Скрещивание. Вся популяция перемешивается и по-порядку по-парам скрещивается. Каким образом? Берутся соответствующие буквы из наборов каждой особи, сравниваются их полезность и в потомка вставляется наиболее полезная. Если полезность равна, то берется из случайного существа. Затем изначально менее приспособленное существо заменялось потомком (чтобы не изменять размер популяции).
Мутации. В каждом существе случайным образом заменяется одна буква.

Жизнеспособной особью я назвал ту из набора букв которой можно без труда составить кроссворд. Буквы вставляются в перекрестки, и затем слова подбираются по шаблонам. Так вот если по какому то шаблону нельзя подобрать слово, то для букв входящих в этот шаблон (те, что в перекрестках) уменьшается их полезность на 1. Т.к. каждая буква находится в двух шаблонах, то соответственно полезность ее может принимать значения только -2, -1 или 0. Если 0 - то буквы считается полезной. Сумма полезностей всех букв образует приспособленность существа. Если она равна 0 - то существо жизнеспособно.

Удивительно, меньше чем за минуту этот нечеткий алгоритм выдал множество вариантов. Для тестирования я использовал шаблон, который привел вначале сообщения. Размер популяции: всего-лишь 256 особей.

Не думаю, что кто-то сейчас будет вникать в то, что я тут написал, но в будущем надеюсь кому-нибудь пригодиться:) Ура:)

← →
Jeer © (2011-07-15 21:01) [53]

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

← →
Дмитрий С © (2011-07-18 11:03) [54]

> Это ему и позволяет применять теорию эволюционного развития
> в бытовой практике.

Это просто нереально как-то. Способ за пару минут дает как минимум 15000 результатов, в отличии от 1 за час и того случайного.

← →
Дмитрий С © (2011-07-18 11:18) [55]

Даже наврал. ~62000 результатов за 120 секунд. Ващеее!:)

Если считать варианты, отличающиеся только в одном месте, например,
мама, папа, баба, лапа, вата, дата, жаба, рама, тара, кара, фара...
то конечно. А если таких мест несколько, то ваще... :)

А если по существу, то, я примерно понял на что вы намекаете.
Слово из 4х букв с двумя перекрестками, в которых стоят буквы "а" во второй и 4ой позициях.
В моем поиске в качестве результата записывается маска ?а?а - и она считается единственным результатом, даже если этой маске соответствует несколько слов.

Иначе говоря из 62000 результатов можно составить кроссвордов намного, на очень много больше 62000, если считать так как предлагаете вы)

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

> Дмитрий С
> В моем поиске в качестве результата записывается маска ?а?а

Тогда я зря намекал, наверно )
Тем не менее, экспериментальный шаблон так и подталкивает
ко всяким там вращениям-отражениям, сдвигам-перестановкам.
Фактически там тиражируется 1-2 найденных решения.
Попробуй в каждом решении упорядочить по алфавиту список масок,
а потом удали все решения-дубликаты. Интересно, сколько останется?

> Удивительно, меньше чем за минуту этот нечеткий алгоритм
> выдал множество вариантов.

А ничего удивительного. Многие хотят выдумать что-то, что решает задачу

а. быстро
б. точно
в. просто
г. и т.д.

Но реально такой "красивый" алгоритм есть только для некоторого (весьма узкого) класса задач. Большинство реальных задач решаются эвристически.

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

> Sha © (18.07.11 20:24) [59]

Результат храниться следующим образом:
Все перекрестки нумеруются по порядку, и буквы стоящие в перекрестках для результата записываются в строку - это строка и есть результат.
Эти результаты записываются в стринглист, для которого
FFoundCharSet.Sorted := True; FFoundCharSet.CaseSensitive := False; // это конечно излишне - все буквы у меня в нижнем регистре FFoundCharSet.Duplicates := dupIgnore;
Количество результатов снимается с FFoundCharSet.Count.
Поэтому все результаты уникальные.
Если же брать в расчет различные преобразования (кажется так они в геометрии называются), то их может быть 8 в этом случае. Просто поделим те же 62000 на 8, получим 7750 - однозначно уникальных, что тоже уже просто мега круто.
На деле действительно - маска некудышная, это и заказачик говорит, на деле маска будет проще и врядли симметричной или типа того, поэтому тратить на это время сейчас, думаю, смысла нет.

P.S. Кстати насчет преобразований я погорячился. их будет меньше 8. Например, если мы отразим кроссворд по горизонтали, то по-той же горизонтали мы уже тех же слов можем и не составить.

> TUser © (18.07.11 23:01) [60]
> Мир устроен сложнее простых моделей.

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

> Дмитрий С © (19.07.11 06:05) [61]
> насчет преобразований я погорячился. их будет меньше 8

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

Когда кирпичами забита вся вселенная и каждый второй из них хороший,
при помощи генетического алгоритма можно построить сотню-другую домов на Земле,
но почти вся цивилизация останется бездомной, не говоря уже о том,
что невозможно получить никакого преставления,
как строить дома на Альфе Центавра.
Если хороших кирпичей во вселенной хватит только на сотню домов,
то на бездомное существование обречено все живое.

> [62] Sha © (19.07.11 09:00)
> Путь из Москвы в Питер через Владик - уже решение.
> Осталось его оптимизировать.

Ехали мы однажды в Москву из Красноярска на поезда - это 3-е суток. Ехал с нами сосед по купе тоже в Москву, но ему надо было куда-то на севера, но из Красноярска самолётом было дороже, чем доехать до Москвы 3-е суток и оттуда самолётом назад куда-там ему надо было. Оптимизация.

> Если хороших кирпичей во вселенной хватит только на сотню
> домов,
> то на бездомное существование обречено все живое.

Ну не думаю, надо просто больше времени :)

> Inovet (19.07.2011 11:03:03) [63]

Наверное водка и еда съели всю оптимизацию

> [65] Anatoly Podgoretsky © (19.07.11 11:24)
> Наверное водка и еда съели всю оптимизацию

Водка была немного, ещё турок ехал в Турцию он быстро уснул и потом не хотел ея. Угол крюка попрямее чем Мск-Владик-Питер, наверно не всю съела.

> Дмитрий С © (19.07.11 11:15) [64]
> Ну не думаю, надо просто больше времени :)

чуть больше, чем возраст вселенной.

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

> Sha © (19.07.11 12:24) [67]

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

> Дмитрий С © (19.07.11 20:06) [68]
> Если взять псевдо кроссворд 5 на 5...

А решение у него есть? Если да, то я бы поискал на досуге )

← →
Дмитрий Белькевич (2011-07-19 23:44) [70]

Для вот этого:

http://ssu.argi.ru/cross.png

Можно было б пару-тройку результатов работы [52] увидеть? Что получилось?

> Sha © (19.07.11 21:19) [69]

Некая програмка Crossword Wizard 2.1 по моему словарю составляет такой кроссворд достаточно быстро.

Вот словарь (просто список)
http://ssu.argi.ru/dic.txt
Определения я стер по понятным причинам.

> Дмитрий Белькевич (19.07.11 23:44) [70]

http://ssu.argi.ru/1.png
http://ssu.argi.ru/2.png
http://ssu.argi.ru/3.png
http://ssu.argi.ru/4.png

> Дмитрий С © (20.07.11 08:10) [71]
> Некая програмка Crossword Wizard 2.1 по моему словарю составляет такой кроссворд достаточно быстро.

Можно на результат посмотреть, чтоб точно знать, что он существует?

> Можно на результат посмотреть, чтоб точно знать, что он
> существует?

http://ssu.argi.ru/cw55.jpg

Спасибо

> Дмитрий С © (21.07.11 13:06) [75]

Кое-какие соображения относительно структуры данных для ускорения перебора имеются. Но нет полной ясности, как должен вести себя алгоритм в такой, например, ситуации. Скажем шаблон в виде гантели представляет собой 2 почти изолированных участка, соединенных перемычкой в одно слово, что-нибудь типа "машиностроение". Человек в подобном случае будет плясать сначала вокруг этого слова, а потом перейдет к краям. Как в алгоритме должно происходить переключение на "ручку гантели" мне пока не ясно. Медитирую во время поездок в метро.

← →
Дмитрий Белькевич (2011-07-22 00:17) [77]

Спасибо, посмотрел.

Мысли первых минут.

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

> 1. Предварительно отсеивать словарь по размеру слов. То
> есть - если заранее известны все размеры слов, которые будут
> использованы, думаю, можно существенно сократить словарь.

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

> 2. Посчитать вероятность

Хорошая мысль применить вероятности. Задумаюсь.

> Sha © (21.07.11 14:00) [76]

Есть успехи?

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

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