- Поисковые системы
- Практика оптимизации
- Трафик для сайтов
- Монетизация сайтов
- Сайтостроение
- Социальный Маркетинг
- Общение профессионалов
- Биржа и продажа
- Финансовые объявления
- Работа на постоянной основе
- Сайты - покупка, продажа
- Соцсети: страницы, группы, приложения
- Сайты без доменов
- Трафик, тизерная и баннерная реклама
- Продажа, оценка, регистрация доменов
- Ссылки - обмен, покупка, продажа
- Программы и скрипты
- Размещение статей
- Инфопродукты
- Прочие цифровые товары
- Работа и услуги для вебмастера
- Оптимизация, продвижение и аудит
- Ведение рекламных кампаний
- Услуги в области SMM
- Программирование
- Администрирование серверов и сайтов
- Прокси, ВПН, анонимайзеры, IP
- Платное обучение, вебинары
- Регистрация в каталогах
- Копирайтинг, переводы
- Дизайн
- Usability: консультации и аудит
- Изготовление сайтов
- Наполнение сайтов
- Прочие услуги
- Не про работу
VK приобрела 70% в структуре компании-разработчика red_mad_robot
Которая участвовала в создании RuStore
Оксана Мамчуева
Авторизуйтесь или зарегистрируйтесь, чтобы оставить комментарий
Небольшое лирическое отступление:
любят же у нас напускать туману и говорить про всяческие ноухау, суперпупер достижения в виде реализованных алгоритмов итд итп, не обозначая конкретных деталей. Чтобы враг денюжку заплатил. Но по моему опыту оно врагу и бесплатно не нужно, а тщательно скрываемые алгоритмы не вполне корректны.
Теперь по делу:
Аристан недавно анонсировал некую идеальную функцию хеширования, которая может быть использована для присвоения словам уникальных номеров, которые зависят только от слова. При этом никакие два слова не имеют одинаковое значение функции!! Упорно отказался прояснить детали.
Тем не менее, вполне очевидно, что функций, имеющих практическое значение, то есть возвращащих значения ну хотя бы в пределах 4-байтного инта не существует. Просто потому, что не очень длинных слов (<20 символов) очень много. И их гораздо больше чем интов. Это значит, что всегда будут два слова с одинаковым значением функции. Итого, заявленная функция не сможет нумеровать произвольные строки. А если вспомнить, что в некоторых коллекциях а-ля медицинские или химические термины часто встречаются длинные слова, и ограничиваться 20 символами нельзя, то даже 8 байтного инта не хватит.
Если сделать предположение, что все генерируемые слова удовлетворяют русской n-граммной статистике (то есть другими словами, данным, что в такой-то позиции слова такой-то длины, при условии того, что этой позиции предшествует такая-то n-грамма могут встречаться далеко не все буквы алфавита), и что таких слов не очень много (а я в ближайшие день два точно посчитаю сколько их и назову цифру), и соответственно придумать какое-нибудь правило нумерации вроде позиционной системы счисления с переменным основанием, с основанием, меняющимся в зависимости от предыдущих разрядов), то все равно это правило будет абсолютно не применимо для интернет поисковика, в котором в силу разных причин слова могут встречаться абсолютно произвольные.
То бишь, в общем случае функция не существует, а существует какой-то паллиатив, который работает на подмножестве всех строк. Что и лишний раз укрепляет мое мнение, что когда напускают туману или алгоритм дохлый или не все корректно с постановкой задачи.
Небольшое лирическое отступление:
все правильно, идеального алгоритма не существует
но зачем же так мучаться - легко предложить алгоритмы, решающие задачу с 99,9% необходимых характеристик и добавить обработку исключений
например, обрабатывать известный словарь - по дереву букв,
а неизвестные класть в хеш (с проверкой)
ну да, иногда будут коллизии, придется искать место - долго, конечно, но редко, очень редко
и все.
может быть имелась в виду потенциально полезная задача создания уникального хэша для известного словаря?
все правильно, идеального алгоритма не существует
но зачем же так мучаться - легко предложить алгоритмы, решающие задачу с 99,9% необходимых характеристик и добавить обработку исключений
например, обрабатывать известный словарь - по дереву букв,
а неизвестные класть в хеш (с проверкой)
ну да, иногда будут коллизии, придется искать место - долго, конечно, но редко, очень редко
Добрый день,
Преимущества у такой хеш-функции есть. Не нужно хранить словарь в памяти, значит освобождается память. Кроме того решается проблема синхронизации хеша неизвестных слов если индексация идет на нескольких машинах параллельно.
С другой стороны не похоже что такая хеш функции существует... А почему бы просто не инкрементировать ID новых слов по мере их появления? А если индексация ведется на нескольких машинах? то выдать каждой свой диапазон ID для присвоения новым словам. И где-то держать центральный словарь с перекодировкой слово --> (ID1, ID2,..)
Тем не менее, вполне очевидно, что функций, имеющих практическое значение, то есть возвращащих значения ну хотя бы в пределах 4-байтного инта не существует. Просто потому, что не очень длинных слов (<20 символов) очень много.
- вот именно: просто потому, что очень много. Хэш, не хэш - никакой роли для этого тезиса не играет!
Аристан недавно анонсировал некую идеальную функцию хеширования,
Не Аристан а Artisan, не хэширования а сжатия, не идеальную а полезную, не анонсировал а вспоминал, ...
когда напускают туману или алгоритм дохлый или не все корректно с постановкой задачи.
Вы опять все перепутали но очень правильно пишете про постановку задачи, речь не идет о счете всех возможных слов, я как раз писал об одной частной задаче решение которой применимо для той темы в которой этот разговор начался.
Пардон с именем ошибочка вышла. Насчет того, что я все перпутал цитирую. Я написал:
есть два варианта
1) хранить, тогда прощай компактное представление. точнее не прощай, но это доп расходны на хранение.
2) генерировать из слова уникальные id. но я не знаю алгоритма, который гарантировал бы уникальность такого id.
Вы написали:
Оба утверждения неправильные, ...
что же я перепутал?
что же я перепутал?
Все что можно было перепутать,
Вы просто думаете в другую сторону, ...
Не надо так сильно волноваться,
инки например колесо не использовали,
и совсем не волновались, ...
Вы лучше поменьше об этом думайте,
чтобы случайно не заболеть, ...
-откуда столько слов? 256^4=4294967296
Насколько я знаю, в русском литературном около 400 тыс. слов максимум. Т.е., в 1000 раз меньше.
Хм, да я не волнуюсь, просто Вы себя дискредитируете. Я Вам уже и процитировал Ваше высказывание, которое однозначно трактуется как, что не существует алгоритма, который позволяет генерировать уникальные айди из слова. И доказательство привел, почему это НЕВОЗМОЖНО. А Вы все говорите, что я ничего не понял. Видимо, просто мужества не хватает признать: да что-то я не так сказал.
PS: Тут надо было бы еще для начало уточнить размер этого айди в байтах. Например все слова из латинских букв длиной 16 символов можно закодировать используя 10 байт. Но Вы даже и это почему-то не сказали. Хотя вряд ли такой способ может быть практически ценным.
-откуда столько слов? 256^4=4294967296
Насколько я знаю, в русском литературном около 400 тыс. слов максимум. Т.е., в 1000 раз меньше.
А причем здесь русский литературный язык? Речь шла о том, как бы сэкономить на хранении номера слова. Способ существует единственный - вычислять этот номер по слову. Но при этом возникает одна трдность некий небольшой процент слов будет иметь одинаковый номер. Артизан утверждает, см цитату выше, что это неправильное утверждение. То есть смотри называние темы.
А раз уж такая функция и существует, то она должна работать не только со словами словарными, но и вообще со всеми словами вообще, которые есть или могут быть в интернете. А их гораздо больше чем 4 миллиарда.
-при том, что 4*10^9 гораздо больше, чем 4*10^5, а вовсе не
-не верю. сколько именно?
-при том, что 4*10^9 гораздо больше, чем 4*10^5, а вовсе не
-не верю. сколько именно?
ну Вы абсолютно правы в том, что 4*10^9 гораздо больше, но еще нужно закодировать правило преобразования слова в число, чтобы каждое слово кодировалось уникальным интом как бы Вы предложили это сделать?
Ответ на вопрос сколько именно: как минимум 28^20
в интернете может встретиться абсолютно любая комбинация латинских букв. И если Вы не верите, то назовите комбинацию и сделаю страничку, которая эту комбинацию содержит!