В далеком (а может и не очень далеком) 1975 году Альфред Ахо и Маргарет Корасик опубликовали статью, в которой был подробно описан алгоритм эффективного поиска всех вхождений всех строк-образцов в заданную строку. В дальнейшем этот алгоритм и получил название «алгоритм Ахо-Корасик». Неудивительно, что через некоторое время появились технические и «художественные» переводы данной статьи на русский язык. Порой мне даже встречались вольные изложения сути алгоритма в том виде, в котором его понимает автор. Причем последний, судя по тексту, узнал об алгоритме далеко не из первоисточника. Я не знаю существовал ли перевод, который послужил первоисточником проблемы, но мне всё больше и больше попадаются статьи с описанием алгоритма Ахо-Корасик, в котором допущена одна и та же кардинальная ошибка. Последней каплей была статья на хабре, которую данная ошибка не миновала. Собственно об этой ошибке мне и хотелось бы рассказать общественности в своей статье.
Перед началом, еще пара слов о целевой аудитории: Скорее всего, тем, кто давно знаком с алгоритмом Ахо-Корасик, моя статья будет не интересна, так как о его особенностях они давно уже знают. По крайней мере, все мои знакомые программисты не один раз применявшие данный алгоритм знают о существовании его неверных интерпретаций не понаслышке. А вот новичкам и тем, кому не довелось часто применять его на практике, эта статья может оказаться довольно полезной.
Итак, начнем.
Читать полностью »
Метка «автомат»
Неверная интерпретация алгоритма Ахо-Корасик
2013-11-13 в 16:14, admin, рубрики: автомат, Алгоритмы, метки: автоматIntel устанавливает в своих офисах кофе и кола автоматы на платформе Core i7
2013-04-01 в 5:13, admin, рубрики: автомат, Блог компании Intel, будущее здесь, кофе, Офисы IT-компаний, метки: автомат, кофе 
Исполнительный вице-президент Intel Дади Перлмуттер тестирует работу кола автомата в центральном офисе компании.
Компания Intel сообщает о начале массового тестирования кофе и кола автоматов нового поколения; на первом этапе оно будет проводиться в собственных офисах. Автоматы построены на платформе Intel Core i7 и оснащены большим количеством дополнительных устройств. У автомата имеется огромный 46-дюймовый сенсорный дисплей с поддержкой мультитача, микрофон, камера высокого разрешения и беспроводной адаптер Wi-Fi.
Читать полностью »