Упрощенные структуры основной части этой главы снабдили нас знаниями, достаточными для перехода к изучению структур данных, применяющихся в промышленных приложениях. Это дополнение посвящено примечательной структуре, использованной Дугом Макилроем для хранения словаря в программе ispell, написанной им в 1978 году. Когда я писал первые варианты глав этой книги в 1980 году, для проверки правописания я пользовался именно программой Макил- роя. Для второго издания я снова воспользовался программой spell и пришел к выводу, что она все еще очень полезна. Подробности о программе Макилроя можно узнать из его статьи «Разработка орфографического словаря» (IEEE Transactions and Communications СОМ-ЗО, 1, Jan 1982, pp. 91-99). В моем толковом словаре «жемчужина» определяется как «нечто избранное или драгоценное» — эта программа вполне подходит под такое определение.
Первая задача, с которой столкнулся Макилрой, состояла в составлении списка слов. Он начал с пересечения полного словаря (для обеспечения правильности) со списком Брауиовского университета объемом в миллион слов. Это было достойное начало, но работы было еще много.
Подход Макилроя лучше всего проявился в том, как он искал имена собственные, которые не включены в большинство словарей. Сначала он занялся человеческими именами: 1000 самых часто встречающихся фамилий из большого телефонного справочника, список мужских и женских имен, известные фамилии (например, Дейкстра и Никсон) и мифологические имена из индекса к одной из книг. Поразмыслив над «ошибками» вроде Xerox и Texaco, он решил добавить в словарь названия компаний из списка 500 наиболее известных. Издательские компании часто встречаются в библиографиях, поэтому он добавил и их. Затем Макилрой занялся географией: страны, их столицы, штаты, столицы штатов, названия ста самых крупных городов США и мира, океаны, планеты и звезды.
Он добавил к словарю названия наиболее распространенных животных и растений, термины из химии, анатомии и информатики. Но ему приходилось быть внимательным, чтобы не добавлять слишком много слов: в словарь не были включены специальные термины, которые могли бы считаться написанными с ошибкой обычными словами (как геологический термин cwm), а когда правильных вариантов написания было несколько, он включал только один из них (traveling, но не travelling ).
Одним из ключей к решению задачи был анализ результатов работы spell с реальными текстами. В течение некоторого времени программа автоматически отсылала ему копии результатов (на компромиссы между конфиденциальностью и эффективностью в те дни смотрели по-другому). Обнаружив ошибку, Макилрой решал ее наиболее общим способом. В результате получился отличный список из 75 000 слов. В него входит большинство слов, используемых мной в письменной речи, и при этом программа обнаруживает мои ошибки.
В программе использовался анализ аффиксов, позволяющий отделять приставки и суффиксы и оставлять одни корни. Это одновременно и необходимо и удобно. Необходимость связана с тем, что полного списка слов для английского языка быть не может; любая программа проверки орфографии должна делать предположения о происхождении слов наподобие misrepresented, либо она будет считать неправильными большое количество нормальных слов. Анализ аффиксов дал положительный побочный эффект, заключавшийся в уменьшении словаря.
Задачей анализа аффиксов является редукция слов наподобие misrepresented до sent, отделяя mis-, re-, рге- и -ed. Хотя слово represent и не означает «показывать заново», a present не значит «отправленный заранее», программа spell все равно использует подобные совпадения для уменьшения словаря. В таблицах программы содержится 40 правил добавления приставок и 30 правил добавления суффиксов. Список из 1300 исключений позволяет отбросить красивые, но неправильные догадки наподобие редукции слова entend (ошибочное написание intend) до еп + tend. Итак, этот анализ позволяет уменьшить словарь из 75 ООО слов до 30 000. Программа Макилроя обрабатывает каждое слово, отбрасывая приставки и суффиксы и проверяя наличие оставшейся части в словаре, до тех пор пока не обнаружится совпадение или не закончатся аффиксы (в последнем случае слово считается написанным с ошибкой).
Предварительные оценки показали, что весь словарь нужно постараться вместить в оперативную память. Это было особенно сложной задачей для Макилроя, который писал свою программу для PDP-11 с 64 Кбайт адресного пространства.
О методах экономии памяти в аннотации к его статье говорится так: «Отбрасывание суффиксов и приставок уменьшает список на треть, хэширование позволяет избавиться от 60% оставшихся битов, а сжатие уменьшает объем еще вдвое». Таким образом ему удалось вместить список из 75 000 английских слов (и приблизительно такого же количества словоформ) в 26 000 16-битных машинных слов.
Макилрой использовал хэширование, чтобы представить каждое из 30 000 слов в 27 битах (чуть позже мы узнаем, почему именно в 27). Рассмотрим работу схемы на списке из пяти слов:
a list of fi ve words
Первый метод хэширования состоит в использовании n-элементной хэш-табли- цы, размер которой совпадает с количеством слов в списке, и функции хэширования, отображающей строку в целое число из диапазона [0, п). Пример функции хэширования для строк будет рассмотрен в разделе 15.1 главы 15. Поле таблицы с номером i указывает на связанный список, содержащий все строки, для которых функция хэширования возвращает значение i. Если пустые списки представить пустыми клетками и предположить, что h (а) = 2, h (list) = 1 и так далее, то таблица для нашего образца списка может выглядеть, например, следующим образом (рис. 13.4).
Опубликовал vovan666
April 17 2013 00:03:53 ·
0 Комментариев ·
3235 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
