Вот ситуация: на дворе 1984 год, и вам поручили написать программу проверки орфографии для нового текстового процессора MS-DOS. Некоторые пользователи, но не многие, будут иметь на своих ПК 640 КБ памяти. Вам необходимо поддерживать системы всего с 256 КБ. Это четверть мегабайта для текстового процессора, редактируемого документа и памяти, необходимой для операционной системы. О, и проверка орфографии.
Для справки, на моем MacBook стандартный словарь в /usr/share/dict/words составляет 2 486 813 байт и содержит 234 936 слов.
Заманчивым первым вариантом является формат данных, который более сжат, чем необработанный текст. Словарь UNIX содержит останавливаться и остановился и остановка, так что есть много повторений. Умная реализация trie могла бы помочь… но нам потребуется значительное уменьшение, чтобы перейти от 2+ мегабайт к сотне К или около того.
На самом деле, даже если бы мы могли представить каждое слово в словаре проверки орфографии как один байт, нам нужны почти все полные 256 КБ только для этого, и, конечно, однобайтовое представление не будет работать. Таким образом, не только хранение всего словаря в ОЗУ выглядит безнадежным, но и хранение фактического словаря на диске только с индексом в ОЗУ выглядит безнадежно.
Теперь становится грязно. Мы могли бы попробовать взять подмножество словаря, содержащее наиболее распространенные слова, и сильно сжать его, чтобы оно поместилось в памяти. Затем мы придумываем более медленный дисковый механизм для поиска остальных слов. Или, может быть, мы перейдем непосредственно к полностью дисковому решению, используя своего рода пользовательскую базу данных (помня также, что мы не можем предполагать, что у пользователя есть жесткий диск, поэтому словарь все еще должен быть записан на дискету 360 КБ). .
Кроме того, нам нужно обрабатывать некоторые другие функции, такие как добавление пользователем новых слов в словарь.
Написание программы проверки орфографии в середине 1980-х было сложной задачей. Программисты придумали несколько впечатляющих методов сжатия данных в ответ на вызов проверки орфографии. Точно так же были некоторые очень умные структуры данных для быстрого поиска слов в сжатом словаре. Это была проблема, решение которой могло занять месяцы сосредоточенных усилий. (И, кстати, сокращение размера словаря с 200 000+ до 50 000 или даже 20 000 слов было разумным вариантом, но даже это не оставляет двери открытой для наивного подхода.)
Перенесемся в сегодняшний день. Программа для загрузки /usr/share/dict/words в хэш-таблицу — это 3-5 строк Perl или Python, в зависимости от того, насколько вы кратки. Поиск слова в этом словаре хеш-таблиц — тривиальное выражение, встроенное в язык. Вот и все. Конечно, вы могли бы придумать какие-то способы уменьшить время загрузки или уменьшить объем памяти, но это обледенение и, скорее всего, не понадобится. Базовая реализация настолько бездумно тривиальна, что может стать упражнением для читателя в одной из первых глав любого учебника по Python.
Это прогресс.
постоянная ссылка 8 июня 2008 г.
