Помощник – «решатель филвордов» на python (алгоритм поиска слов плюс распознавание текста tesseract)

[OlegFX]

Писал когда-то подобное для 4*4 на Go — только ищет всё, потому что делает полный перебор рекурсивно. Правда, мультипоточность и хитрый старт поиска. Только что проверил время поиска на 4-ядерном макбуке с использованием словаря на 99431 слов:

4*4 — Execution time: 1.323269ms

[zxgame]

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

Не могли бы вы поделиться "хитрым стартом поиска", заинтриговали) т.к. Execution time: 1.323269ms прям взбодрили меня.

[OlegFX]

Для начала - подготовка словаря. Я создавал слайс:

dict [][]string // [аб]аббатский

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

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

Так как массив отсортирован - можно искать только пока префикс текущего слова в списке "меньше" найденной комбинации букв (я этого не делал, но это ещё ускорило бы поиск).

[OlegFX]

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

var ultrafastDict [][]WordsStruct // [аббат]аббатский

type WordsStruct struct {
	isWord bool
	isPrefix bool
	subWords []string
}

Первые 5 букв слова образуют индекс в слайсе ultrafastDict. В алфавите 33 буквы, так что слайс для всех возможных комбинаций букв имел бы размер 33 ^ 5 = 39,135,393 элементов.

Если мы ищем слово до 5 букв включительно (а это подавляющее количество поисков для данного алгоритма) - нам достаточно достать элемент под индексом, образующимся из данной комбинации букв, и проверить в нём поля isWord (данная комбинация букв является словом) и isPrefix (данная комбинация букв является префиксом для других слов). Если же мы ищем слово из комбинации больше 5 букв - ориентируемся уже на массив subWords - как в алгоритме, который я описывал выше.

[OlegFX]

Там, конечно, ошибка в объявлении ultrafastDict. Правильная версия:

var ultrafastDict []WordsStruct // [аббат]аббатский

Либо через указатели, чтобы сэкономить память (но не GC):

var ultrafastDict []*WordsStruct // [аббат]аббатский