а нельзя ли эту тему вынести из данного форума?
В ru_ir опубликована фотография полки. Список же дан в комменте в ответ на просьбу подписать неразборчивые названия.
Коммент и "публикация" в сообществе - разные вещи.
Этот список делался методом копи-пейста из вики-файла. Нет в нем никакого сермяжного смысла, кроме попытки как можно быстрее "подписать" фотку. Еще раз: это подпись к фотке, а НЕ список рекомендованной литературы, никоим образом он НЕ претендует на полноту, вообще ни на что НЕ претендует. Еще раз: это НЕ мои любимые книги, а подпись к фотографии. Никакую из категорий этот список НЕ покрывает никаким образом. (просто шагу не ступить, блин, жуть какая-то).
Спасибо всем большое за поздравления!
Постараюсь соответствовать.
Илья
(вечером иду слушать джаз - Билли Кобэма. Если считать, что для любителей джаза Майлс Дэвис - Иисус Христос, то Билли Кобэм - это примерно апостол Павел :) )
AOL-овский алгоритм
(в сторону: С.В. Ильинский - сын В.И.Левенштейна).
С позволения Сергея изложу кратко здесь.
Пусть "частота" это нормированная внутридокументная частота слова в документа (TF), лежащая в диапазоне 0..1, где 1 частота самого частого слова в документе.
Для каждого слова (однократно) строится распределение документов по такой внутридокументной "частоте".
Алгоритм составления лучшей выборки выглядит так.
Проводим несколько итераций, каждая из которых состоит из двух фаз (1) и (2).
В (1) максимизируется покрытие при фиксированной (ограниченной снизу) точности в (2) максимизируется точность при фиксированном покрытии.
Определим "точность" слова следующим образом: "точность" тем выше, чем меньше встречаемость слова "в дельте-окрестности данного значения частоты" (то есть чем меньше документов с TF равным TFthreshold+-delta). Частоту с наилучшей "точностью" мы называем пороговой и запоминаем для дальнейшего использования в алгоритме (см статью).
После каждой итерации отбрасываем самые "плохие" слова. После последней итерации оставляем достаточно слов для хорошего покрытия.
Этот метод, позволяет, начав с выборки в сотни тысяч слов (см, например, статьи ребят из AOL-а, которые на этом и остановились), оставить набор в 3-5 тысяч, расчет сигнатур по которому с применением полнотекстового индекса осуществляется на миллиардном индексе несколько минут (на нескольких машинах, естественно).
К большому сожалению это все еще нигде не изложено (нет времени), поэтому если будете использовать идею в статьях, просьба обязательно давать ссылку на Яндекс и С.В.Ильинского.
Всем привет.
Интервью действительно "ни о чем". Иногда ответы соответствуют вопросам, иногда их обтекаемость диктуется условиями игры. Морду "кирпичом" старался не делать.
В выпадениях страниц особых проблем для пользователя не вижу.
Ошибочные забанивания сайтов случаются, но во-первых механизм разбанивания работает, во-вторых, ошибки мы видим и исправляем.
не знаю насчет "SQL" и "100 раз", но с BerkeleyDB и аккуратной блочной упаковкой достигали всего лишь двойной деградации.
Это тоже немало конечно, в случае с каким-нибудь Google каких-то 120 тысяч серверов. :)
Леня, чего там гадать. Эта старинная статья с Диалога-95, про то как была упакована моя морфология в эпоху Библейского Компьютерного Справочника. Там же все подробнейшим образом написано и ссылка на Макилроевcкий ispell имеется.
Идешь в Яндекс, смотришь на полку с книжками, открываешь тоненькую книжечку "Жемчужины стиля программирования" Бентли (оба русских издания и хоть старое МИР-овское, хоть новый "кошмар переводчика") и читаешь там изложенную на русском языке историю как МакИлрой делал испелл и как он упихал анлицкий словарь в 50 килобайт.
Вкратце: "VBC-упакованная" (*) "сблокированная, с субиндексом" (**) "кишка" (***) "хешей" (****) основ слов.
(*) "VBC-упакованная" = здесь наверное объяснять не надо
(****) "хеш" - хеш-функция по большому основанию, то есть в разреженной (sparsed) таблице, чтобы вероятность коллизии была близка к нулю: я брал в районе 2^12 умн. на размер словаря, что давало 2 или 3 коллизии, кажется, в статье есть. То есть 140 тысяч основ*4 тысячи = примерно 500 миллионов. Поскольку используется VBC, то грубо, столько примерно бит (12) и потребуется на 1 основу.
(***) "кишка" - отсортированный по возрастанию разностно-упакованный массив (внутрияндексный термин)
(**) "сблокированная, с субиндексом" - внутрь кишки в начало блоков по несколько килобайт, "смотрит" табличка указателей, то есть субиндекс. Чтобы при поиске слова не распаковывать всю кишку, а бежать только от начала блока
Естественно тексты там не хранятся, синтез невозможен, это все в статье есть, несловарные слова в БКС оставлялись текстами и тд
а) "Блочно-слотовая": это вот что. Тогда, в старые-старые времена (1993 год), диски были медленные и памяти было мало, а процессор торомзил. В память читали файл по "блокам". Внутри блоков (то есть единиц обмена информации с жестким диском) для скорости работы процессора и при этом все еще хорошей упаковки, часто устраивась более мелкая блокировка, которую можно условно назвать "слотами" (гнездами).
Например; "блок" - это килобайты (0.5-16, типично 4), а "слот" - скажем 32-256 (типично 32 или 64) байт.
В каждом слоте данные лежат с "инкрементальной упаковкой", так как весь блок распаковывать дорого.
Понятно, что "послотовый" обмен с диском слишком невыгоден: требуется слишком большое оглавление, а файловая система все равно производит обмен не меньше размера сектора или кластера.
Т.о. "Блок" - единица обработки данных для диска, а "слот" - единица обработки данных для процессора.
б) старался писать понятно.
в) Когда я писал эту статью (март 1995), у меня еще не было интернета (он у меня появился в сентябре, а читать статьи я начал в ноябре), статьи появились в сети гораздо позже (siteseer открыли году в 1998, а наполненным он стал не раньше 2000-го, pdf тогда еще не индексировались). Возможно, что я тогда, 10 лет назад, неточную ссылку поставил.
Помню первый грант нашей студии (сколько-то сот долларов, кажется :)) на кисточки, краски, ватман и тп, мы получили в 1994 году от GlaxoWelcome (теперь SmithGlaxoWelcome кажется) именно через CAF.
И что тут грязного? И кто тут что отмывал?
