Чтобы найти слово w, программа обращается к биту h(w). Если этот бит сброшен, программа сообщает, что слова w в таблице нет. Если бит равен 1, программа делает предположение, что слово w в таблице есть. Иногда функция хэширования дает для ошибочного слова то же значение, что и для правильного, но вероятность такой ошибки 30 000/227, то есть около 1/4000. В среднем каждое из 4000 неправильных слов будет сочтено правильным. Макилрой предположил, что в типичном черновике содержится не более 20 ошибок, поэтому дефект будет проявляться не чаще, чем в одном из сотни документов, — поэтому он и выбрал число 27.
Представление таблицы строкой из п = 227 битов потребовало бы более 16 миллионов байтов. Поэтому в программе хранятся только единичные биты. В приведенном ранее примере были бы сохранены значения 5, 10, 13, 18, 22. Слово w считается присутствующим в таблице, если в этой последовательности имеется значение h(w). Очевидное представление подобной последовательности потребовало бы 30 000 27-битных слов, но в компьютере Макилроя было всего лишь 32 000 16-битных, поэтому он отсортировал список и использовал код переменной длины для записи разностей между соседними значениями. Предполагая наличие фиктивного нулевого начального значения, мы получили бы новую последовательность: 5, 5, 3, 5, 4. Разности в программе Макилроя занимали в среднем 13,6 бит каждая. При этом оставалось несколько сотен лишних слов памяти, которые были отведены на указатели на некоторые точки в сжатом списке, что позволяло ускорить процесс поиска. Таким образом, получился словарь объемом 64 Кб, малым временем доступа и малой вероятностью ошибки.
Мы уже упомянули о двух достоинствах программы spell: она дает полезные результаты и словарь помещается в адресном пространстве. Помимо этого, программа была еще и быстрой. Даже на древних компьютерах, для которых она была впервые написана, проверка статьи в десять страниц требовала полминуты, а книгу вроде этой программа проверила бы за десять минут (что в те годы казалось безумно быстрым). Правописание одного слова можно было проверить за несколько секунд, поскольку маленький словарь можно было быстро считать с диска.
Опубликовал vovan666
April 17 2013 00:03:57 ·
0 Комментариев ·
3219 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.