Алгоритм расстановки переносов с использованием фильтра Блума

Классический пример яркости фильтров Блума - в алгоритмах расстановки переносов. Это даже пример, приведенный в исходной статье о фильтрах Блума.

Я не понимаю, как фильтр Блума будет использоваться в алгоритме расстановки переносов.

Алгоритм расстановки переносов определяется как нечто, что берет входное слово и возвращает возможные способы переноса этого слова.

Будет ли фильтр Блума содержать как hyph-enation, так и hyphena-tion, а клиентский код будет запрашивать фильтр для h-yphenation, hy-phenation, hyp-henation, ...?

Вот что говорится в оригинальной статье:

Пример приложения "Анализ расстановки переносов"

[...] Предположим, что программа содержит около 500 000 слов, которые можно расставить через дефис, и что 450 000 из этих слов можно расставить через дефис, применив несколько простых правил. Остальные 50 000 слов требуют обращения к словарю. Разумно оценить, что в среднем потребуется не менее 19 битов для представления каждого из этих 50 000 слов с использованием обычного метода хэш-кодирования. Если мы предположим, что коэффициент времени T = 4 является приемлемым, мы находим из ур. (9) размер хэш-области должен составлять 2 000 000 бит. Это вполне может быть слишком большим для практической хэш-области, содержащейся в ядре. Используя метод 2 с допустимой частотой ошибок, скажем, P = 1/16, и используя наименьшую возможную хеш-область, имея T = 2, мы видим из ур. (22), что проблема может быть решена с помощью хэш-области менее 300000 бит, размер, который, скорее всего, будет подходить для основной хеш-области. При выборе P 1/16 доступ к резидентному словарю на диске потребуется примерно для 50 000 + 450 000/16 ~ 78 000 из 500 000 слов, которые должны быть расставлены через дефис, то есть примерно в 16 процентах случаев. Это составляет сокращение на 84 процента количества обращений к диску по сравнению с тем, которое требуется при типичном традиционном подходе с использованием полностью резидентной хэш-области и словаря на диске.


bloom-filter hyphenation
person aioobe    schedule 14.11.2019    source источник

Ответы (1)


arrow_upward
1
arrow_downward

В этом случае

  • словарь хранится на диске и содержит все слова с правильной расстановкой переносов,
  • фильтр Блума содержит только ключи, требующие специальных переносов, например может быть сам hyphenation,
  • фильтр Блума отвечает «возможно» или «нет».

Тогда алгоритм поиска возможных переносов слова следующий:

word = "hyphenation"; (or some other word)
x = bloomFilter.probablyContains(word);
if (x == "probably") {
    lookupInDictionary(word).getHypenation();
} else {
    // x == "no" case
    useSimpleRuleBasedHypenation(word);
}

Если фильтр Блума отвечает «возможно», то алгоритм должен будет выполнить чтение с диска в словаре.

Фильтр Блума иногда отвечает «возможно», если на самом деле нет специальных правил, и в этом случае дисковый ввод-вывод выполняется без необходимости. Но это нормально, если это не происходит слишком часто (количество ложных срабатываний невелико, например, 1/16).

Фильтр Блума, так как он не имеет ложноотрицательных результатов, никогда не ответит «нет» в случаях, когда имеют специальные расстановки переносов.

person Thomas Mueller    schedule 15.11.2019
comment
Хорошо, если я правильно понимаю, сам фильтр Блума не имеет ничего общего с фактической расстановкой переносов. Он просто используется как защита от ненужного выполнения дорогостоящей операции. - person aioobe; 15.11.2019
comment
Да, я так понимаю этот абзац. - person Thomas Mueller; 17.11.2019