Эффективный поиск слов в строке

Question

У меня есть словарь, содержащий список слов, и у меня есть строковый URL. Я хочу найти все слова, содержащиеся в URL, после того, как он был разложен на токены с использованием разделителей. Прямо сейчас, я проверяю каждое слово в словаре на каждый токен больше определенного числа (используя функцию String содержит java). Например, я ищу слова типа «земля» в wunderground для www.wunderground.com

Я уверен, что есть более эффективный способ сделать это. Есть идеи?

Answer 1

Если вы загружаете словарь в HashMap, вы можете протестировать каждую подстроку кандидата («wunderground», «underground», «nderground», «derground», ..., «wundergroun», ..., «under ", ..." ground ", ...) очень быстро, в частности, в O (1) раз.

Для оценки эффективности: Выясните, сколько шагов ему нужно сделать. Мы оценим его большую сложность O.

Ваш текущий алгоритм должен прокручивать весь словарь: работа пропорциональна размеру словаря, записи D). Для каждого словаря слово вызывает : работа пропорциональна размеру URL-слова, символам C, минус средний размер словарного слова, который мы будем называть 5. Таким образом, он принимает порядок D * (C - 5) шаги, O (D * (C - 5)), для каждого слова в URL.

После создания хеш-таблицы стоимость поиска не зависит от количества записей. Каждый URL-адрес символов C имеет C подстроки. Если вы обрезаете его подстроками не менее 5 символов, это (C - 5) подстроки. [Ну, технически это (C - 5) * (C - 4)/2, но мы вычисляем асимптотическую сложность, что является приближением большой картины.] Таким образом, стоимость поиска их всех в словаре - это (C - 5) шаги. Опять же, это для каждого слова в URL-адресе и независимо от размера словаря.

Скажем, ваш словарь содержит 10 000 записей, а средний URL-адрес - 10 символов. Затем старый алгоритм принимает 50 000 шагов на URL-адрес, а алгоритм hash принимает 25 шагов на URL-адрес. Имеют смысл?