Навигация
Главная
Поиск
Форум
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
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Создание отчето... 65061
Модуль Forms 64836
Пример работы с... 63242
ТЕХНОЛОГИИ ДОСТ... 61551
Имитационное мо... 57391
Реклама
Сейчас на сайте
Гостей: 6
На сайте нет зарегистрированных пользователей

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

Меры близости на векторах в Delphi + Блок схемы
Создание последовательности окон и передвижение окон по экрану на Turbo ...
Диплом - база данных поставщиков на Delphi (MS Sql Server)+ Пояснительна...

Реклама



Подписывайся на 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 Комментариев · 2248 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
FilesInfo
Delphi на примерах
PHP 5 для "чайников"
SendSMS для PHP-F...
MicroGPSS Studen ...
Быстрое создание ...
Приемы программир...
isoCanvas (Редакт...
AntiRus
Медиа комбайн
Иллюстрированный ...
AJAX и PHP. разра...
AlnComponents
Pass [Исходник на...
DirHTMLReportBuil...
Введение в станда...
Краснов М. - Open...
Доступа к БД Fire...
Фундаментальные а...
Популярные загрузки

Топ загрузок
Приложение Клие... 100466
Delphi 7 Enterp... 86620
Converter AMR<-... 20077
GPSS World Stud... 12644
Borland C++Buil... 11755
Borland Delphi ... 8555
Turbo Pascal fo... 7037
Visual Studio 2... 4998
Калькулятор [Ис... 4760
FreeSMS v1.3.1 3541
Случайные статьи
Методы класса
Женская психология
Таблицы (Table)
Особенности примен...
административных п...
Построение дерева ...
Напряжение сигнала...
Обычные и постоянн...
пользователей,ш; с...
Алгоритм с унарным...
Способы обнаружени...
Потерявшееся окно
Содержание
Проектирование гра...
Г-слоя в физике пл...
ASSIGN (ПРИСВОИТЬ)
Внутренний процесс...
Реализации Drag&Dr...
Использование реги...
1.3.2. Создание об...
OpenGL. Шесть куби...
Задачи, стоящие пе...
Руководитель долже...
Фантомные файлы. 2
Local object types...
Статистика



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


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