⚡ Сегодня мы поговорим об алгоритме Ахо-Корасик, созданном для решения задач, связанных с поиском подстрок в тексте. Садитесь поудобнее - мы начинаем
▪️ Начнем издалека. Представьте, что Вы работаете в секретной службе, и Ваш шеф ставит новую задачу. У Вас есть некоторые данные прослушки (живой текст), среди которых надо искать некоторые ключевые слова. Например, "комитет" и "децифровизация" - почему бы и нет!
▪️ Какие у нас варианты? Наверное, самое простое - каждый раз обходить текст и смотреть, встретилось ли наше заветное слово. Да, это будет работать. Но есть два косяка. Первый - на каждое слово придется заново пересматривать текст. Второй - размер текста постоянно растет, потому что мы кого-то подслушиваем. Как быть?
▪️ Здесь-таки на помощь и спешит алгоритм Ахо-Корасик, разработанный в 1975 году Альфредом Ахо и Маргарет Корасик. Ученые выдвинули смелую гипотезу, которую позже представили в виде алгоритма - будем искать не слова в тексте, а текст в словах.
▪️ Что это значит? Представим себе текст "abcdef" и ключевые слова "bc" и "cd". Берем первую букву - "a". Ни одно из слов на нее не начинается, поэтому идем дальше. Получаем букву "b". На нее начинается слово "bc" - отлично. Запоминаем и идем дальше. И вот перед нами "c". С учетом предыдущего шага мы нашли ключевое слово! Сигнализируем об этом - и идем дальше.
▪️ Настает очень ответственный момент - новая буква. Мы точно знаем, что на предыдущем шаге мы нашли "bc". Если мы добавим новую букву "d", то обнаружим, что ни одно из ключевых слов не начинается на "bcd". Тогда давайте начнем отбрасывать начало до тех пор, пока мы либо не найдем совпадение, либо не опустошим слово. Убираем первую букву и вуаля - мы нашли слово "cd".
▪️ Дальше действуем по той же логике. Следующая буква - "e". Начинаем удалять начало из ранее найденного слова. В конце концов, оно станет пустым, потому что ни одно из ключевых слов не содержим букву "e".
▪️ Продолжая, мы быстро и в режиме реального времени будем находить все нужные слова. Разработчики алгоритма добавили под эту простую логику математические методы, за счет чего и появился знаменитый в мире IT алгоритм Ахо-Корасик. Несмотря на возраст, он до сих пор используется в самых разных областях, включая поисковые системы и редакторы текста.
👉 Подписывайтесь на нас в Telegram:
- https://t.me/antidigitalization
#antidigital_history