Помогите в составлении словаря для игры

[Andrew771]

Привет всем!

Сейчас доделываю игру "Эрудит", код уже написан на 100%. Заставка нарисована ALKO. Осталось только добить словарь из слов русского языка. Нашел в инете словарь существительных в формате txt, но в нем много мусора, всяких "левых" слов, уменьшительно-ласкательные формы, узкоспециальные термины и прочее. Занимаюсь сейчас подчищением, дошел от буквы "А" до буквы "П" - это только половина, а потратил чистого времени дней десять (около месяца "грязного" времени).
Помогите, кто чем может, почистить словарь. Файл выкладываю от буквы "Р" до "Я". Слова только от 2 до 8 букв.

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

В среднем, выкидывается четверть-треть словаря, т.е. сильно выкидывать тоже не нужно. А то скучно будет играть. :)
Я проверяю сомнительные слова по Википедии.

Если каждый возьмет хотя бы по одной букве, то за пару дней можно всё добить. :) Ну а если нет, то я потихоньку движусь.

[Andrew771]

Да, и самое главное забыл: ваше имя будет вписано в анналы (заставку). :)

[scl^mc]

буква "я"

[scl^mc]

буква "ю"

[scl^mc]

буква "э". глаза в кучу :v2_dizzy_botan::v2_dizzy_roll:

[Andrew771]

буква "э". глаза в кучу
во-во, у меня тоже каждый раз так :)
За помощь огромный респект. Будем двигаться навстречу, я на середине буквы П сейчас.

[scl^mc]

буква "щ"

[scl^mc]

буква "ш"

[Andrew771]

Букву П я добил, перешел на букву Р

01.02.2012
- буква Р готова

[Andrew771]

Буква С добита!
Осталась тяжелая буква Т и дальше небольшие от У до Ч. Я за Т принимаюсь.
scl^mc, добьем вместе? В качестве поощрения могу тебе выслать текущую версию игры. :)

[scl^mc]

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

[Andrew771]

я постараюсь сегодня-завтра сделать по максимуму
спасибо!!
E-mail свой можешь кинуть в личку, я тебе вышлю игру?

[scl^mc]

буква "ч". :v2_dizzy_roll:

[scl^mc]

буква "ц"

[Andrew771]

Буква Т готова. Перешел на У.

[Andrew771]

Буква У готова. Перешел на Ф.

[scl^mc]

"х"

[Andrew771]

Супер! Я доделываю Ф, и всё у нас есть!
Правда, словарь еще раз придется почикать на 10%, т.к. нужно уместить в 34500 байт. Удалю малоизвестные слова.

[scooter]

Супер! Я доделываю Ф, и всё у нас есть!
Молодцы !
Жду игру с нетерпением.

[Vitamin]

Правда, словарь еще раз придется почикать на 10%, т.к. нужно уместить в 34500 байт.
Результат мне дайте потом, я попробую пошаманить:)

[Andrew771]

Результат мне дайте потом, я попробую пошаманить
Словарь уже архивированный. Архиватор тоже выложу.
Все буквы уже сделаны, теперь сокращаю. Скоро будет!

[Vitamin]

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

[Andrew771]

Даю все наработки по архивированию словаря (см.файл-архив).


Сейчас алгоритм такой:

Слова сортируются по количеству букв и по алфавиту.

Слова разбиваются по блокам words_2 ... words_8, в каждом блоке только слова с указанным количеством букв (от 2 до 8).

Каждый блок содержит:
- заголовок с количеством слов в блоке (2 байта);
- последовательность битов архивированных слов.

Формирование последовательности битов:

1.
- если текущее слово не имеет одинаковую первую букву с предыдущим словом, то вставляется последовательность битов 000;
- если текущее слово имеет 1 одинаковую первую букву с предыдущим словом, то вставляется последовательность битов 001;
- если текущее слово имеет 2 одинаковых первых букв с предыдущим словом, то вставляется последовательность битов 10;
- если текущее слово имеет 3 одинаковых первых букв с предыдущим словом, то вставляется последовательность битов 11;
- если текущее слово имеет 4 одинаковых первых букв с предыдущим словом, то вставляется последовательность битов 010;
- если текущее слово имеет 5 одинаковых первых букв с предыдущим словом, то вставляется последовательность битов 011.
(Для первого слова блока записывается последовательность битов 000).

2. Оставшиеся неодинаковые буквы текущего слова записываются последовательно своими 5-битными кодами.

3. Переход к следующему слову и п.1.

---

Исходный словарь еще не до конца подчищен от лишних слов.
Нужно всё уместить в 34500 байт.
Сейчас пока получается около 38000 байт. Подсчитал, получается с текущим алгоритмом, чтобы уместиться в 34500 байт, нужно около 13500 слов в словаре.

[Andrew771]

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

---------- Post added at 13:28 ---------- Previous post was at 13:25 ----------

Хотя, можно и убрать требование разбиения на блоки. Но тогда нужно знать длину каждого читаемого слова.

[Vitamin]

К сожалению, мои методы дали худший результат: 55146 и ~85000 для dizpack и токенизации соответственно.

[Andrew771]

Дело в том, что словарь - это не просто текст с повторяющимися словами или комбинациями символов, так что методы архивирования текста тут не подходят.

---------- Post added at 11:38 ---------- Previous post was at 11:19 ----------

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

[goblinish]

а база Пастухова не поможет? на укроторренте валяется 10гигов.
или как вариант ElcomSoft DreamPack 2010+словари.

[Andrew771]

база Пастухова не поможет?
придумай алгоритм кодирования сотен миллионов слов в 48к :)

[goblinish]

придумай алгоритм кодирования сотен миллионов слов в 48к :)
курить алгоритмы компрессии?

Может и оффтоп, но у меня от Verizon была игруха наподобие "Эрудита", так та трехбуквенные аббревиатуры прокатывало. иногда SEX мелькал:v2_dizzy_roll:

[Andrew771]

Проблема в том, что в русском языке средняя длина слова больше 6 букв, в английском 4-5. Пока удается уместить 13500 слов на 48к, что неплохо. На 128к значительно больше можно. В английском Эрудите для Спектрума - Scrabble http://www.worldofspectrum.org/infoseekid.cgi?id=0004375 - около 12000 слов, это притом, что можно использовать любые падежи, формы и прочее, чем и пользуется их алгоритм (я заглядывал в код). Не оптимально у них. :) В русском языке можно использовать только нарицательные существительные в именительном падеже.

[Andrew771]

У меня есть мысль, что если не разбивать на блоки по числу букв в слове, то будет еще большее сжатие по моему алгоритму, т.к. больше будет одинаковых букв между соседними словами.
Моя теория подтвердилась! Написал новый архиватор по этому алгоритму, 14969 слов упаковалось в 36722 байта, а по старому алгоритму - в 38617. Теперь пишу дизархиватор на асме, а количество слов в словаре уже можно смело увеличить до 14000.

[Vitamin]

Есть результаты выделения общих фрагментов. Если поможет- могу поделиться.

[Andrew771]

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

[Vitamin]

да, давай, интересно.
В аттаче результат. Все идентификаторы TOK_* - это наиболее употребительные фрагменты исходных строк (разбитые по длине блоки из склеенных слов). Параметры поиска- от 3 до 16 символов на фрагмент (реально получилось до 6), минимум 3 ссылки на фрагмент.

Если что, смотри тут http://zx.pk.ru/showthread.php?t=9429 на предмет инструментария и описания.

[Andrew771]

Посмотрел твои разработки. Всё-таки не очень жмется словарь токенизацией, т.к. относительно мало их повторов. Я уже и раньше думал над этим. Где-то в 1.5-2 раза только удается сжать.

А я наконец написал распаковщик в игре для своего алгоритма. Работает хорошо, но медленно. Только за минимум 3 минуты обдумывания хода компьютер находит хорошие слова из 4-5 букв. До обдумывания слов из 7-8 букв не успевает даже доходить. :(

---------- Post added at 15:46 ---------- Previous post was at 15:45 ----------

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

---------- Post added at 15:49 ---------- Previous post was at 15:46 ----------

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