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

Вид для печати

25.01.2012, 15:52
Andrew771

Вложений: 1

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

Привет всем!

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

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

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

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

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

Вложений: 1

буква "я"
27.01.2012, 19:38
scl^mc

Вложений: 1

буква "ю"
27.01.2012, 19:59
scl^mc

Вложений: 1

буква "э". глаза в кучу :v2_dizzy_botan::v2_dizzy_roll:
28.01.2012, 21:42
Andrew771

Цитата:

Сообщение от scl^mc

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

во-во, у меня тоже каждый раз так :)
За помощь огромный респект. Будем двигаться навстречу, я на середине буквы П сейчас.
29.01.2012, 11:06
scl^mc

Вложений: 1

буква "щ"
29.01.2012, 11:52
scl^mc

Вложений: 1

буква "ш"
31.01.2012, 16:13
Andrew771

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

01.02.2012
- буква Р готова
06.02.2012, 17:33
Andrew771

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

я постараюсь сегодня-завтра сделать по максимуму
07.02.2012, 13:41
Andrew771

Цитата:

Сообщение от scl^mc

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

спасибо!!
E-mail свой можешь кинуть в личку, я тебе вышлю игру?
08.02.2012, 20:07
scl^mc

Вложений: 1

буква "ч". :v2_dizzy_roll:
09.02.2012, 21:08
scl^mc

Вложений: 1

буква "ц"
10.02.2012, 13:07
Andrew771

Буква Т готова. Перешел на У.
10.02.2012, 15:08
Andrew771

Буква У готова. Перешел на Ф.
10.02.2012, 23:49
scl^mc

Вложений: 1

"х"
11.02.2012, 17:02
Andrew771

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

Цитата:

Сообщение от Andrew771

Супер! Я доделываю Ф, и всё у нас есть!

Молодцы !
Жду игру с нетерпением.
19.02.2012, 00:12
Vitamin

Цитата:

Сообщение от Andrew771

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

Результат мне дайте потом, я попробую пошаманить:)
20.02.2012, 13:52
Andrew771

Цитата:

Сообщение от Vitamin

Результат мне дайте потом, я попробую пошаманить

Словарь уже архивированный. Архиватор тоже выложу.
Все буквы уже сделаны, теперь сокращаю. Скоро будет!
20.02.2012, 18:07
Vitamin

Цитата:

Сообщение от Andrew771

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

Тогда оригинал дай (типа все слова). И требования по доступу к этой базе (типа последовательный просмотр или произвольный доступ к любому слову).
21.02.2012, 10:40
Andrew771

Вложений: 1

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

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

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

Слова разбиваются по блокам 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 слов в словаре.
21.02.2012, 13:28
Andrew771

Цитата:

Сообщение от Vitamin

И требования по доступу к этой базе (типа последовательный просмотр или произвольный доступ к любому слову).

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

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

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

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

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

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

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

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

Цитата:

Сообщение от goblinish

база Пастухова не поможет?

придумай алгоритм кодирования сотен миллионов слов в 48к :)
24.02.2012, 19:45
goblinish

Цитата:

Сообщение от Andrew771

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

курить алгоритмы компрессии?

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

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

Цитата:

Сообщение от Andrew771

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

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

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

Цитата:

Сообщение от Vitamin

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

да, давай, интересно.
27.02.2012, 23:10
Vitamin

Вложений: 1

Цитата:

Сообщение от Andrew771

да, давай, интересно.

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

Если что, смотри тут http://zx.pk.ru/showthread.php?t=9429 на предмет инструментария и описания.
28.02.2012, 15:49
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 ----------

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