Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Пример работы с... 65535
Содержание сайт... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Создание отчето... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Модуль Forms 65437
ТЕХНОЛОГИИ ДОСТ... 62417
Имитационное мо... 58032
Реклама
Сейчас на сайте
Гостей: 6
На сайте нет зарегистрированных пользователей

Пользователей: 13,089
новичок: duskob67
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Двунаправленный динамический список на Delphi + Блок схемы
Калькулятор на Delphi с переводом в другую систему исчисления + Блок схемы
Моделирование вычислительного центра на GPSS + Отчет + Блок схема

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании
13.8. Примеры поиска
Упрощенные структуры основной части этой главы снабдили нас знаниями, достаточными для перехода к изучению структур данных, применяющихся в промышленных приложениях. Это дополнение посвящено примечательной структуре, использованной Дугом Макилроем для хранения словаря в программе 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 04:03:53 · 0 Комментариев · 2307 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
Нет комментариев.
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
Файловый менеджер
Библиотека програ...
Иллюстрированный ...
AboutSystem
Delphi 6/7 базы д...
PDA версия сайта
PHP 5. Практика с...
Х. М. Дейтел, П. ...
AddPage [Исходник...
Ведение справочны...
начисление процен...
Пример работы с р...
DragMe [Исходник ...
Proeffectimage
Черный круг двига...
ShadelLabel
Применение фильтр...
Visual Basic Script
FreeNet
Win-Prolog 3.618

Топ загрузок
Приложение Клие... 100474
Delphi 7 Enterp... 87521
Converter AMR<-... 20081
GPSS World Stud... 13128
Borland C++Buil... 11947
Borland Delphi ... 8638
Turbo Pascal fo... 7042
Visual Studio 2... 5002
Калькулятор [Ис... 4863
FreeSMS v1.3.1 3544
Случайные статьи
Объекту DataAdapte...
Определение вторич...
Разработать и реал...
Этап 2 - перенос о...
Сейшелы
Спил деревьев
Микроконтроллер Ad...
Изображения для пр...
РЕЖИМ "ПОПОЛНЕНИЕ ...
Этот элемент управ...
администрирование—...
Ключевые слова
ВОПРОСЫ ИЛИ ЦЕЛЕВЫ...
Обобщенное програм...
ни один пользовате...
Тонкости дизассемб...
Инфраструктура нас...
Анонимный доступ г...
3.1. Структурирова...
Studio, то объект ...
потенциальный пар...
Меню фотоаппарата ...
Создание иконки пр...
Структура базы данных
Методы-операции де...
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?