В таких сценариях, как форумы и чаты, чтобы обеспечить опыт пользователя, нам часто нужно блокировать много плохих слов. Для единого поиска ключевых слов он, естественно, более эффективен в индексе и обычных методах. Однако, если есть много ключевых слов, если вы неоднократно вызываете индекс или обычные слова, чтобы соответствовать полному тексту, потребление производительности очень высокое. Поскольку целевая строка обычно имеет большую по размеру, необходимо убедиться, что результат получен в одном обходе. Основываясь на таких потребностях, легко подумать о способах соответствия каждого символа во всем тексту в последовательности. Например, для этого текста: «Майк Джордан сказал:« Просто делай это », так что Марк был программистом». Если наше ключевое слово - «Mike» и «Mark», то вы можете пройти все предложение. Когда вы найдете «M», посмотрите, сможете ли вы соответствовать «I» или «A». Если вы сможете соответствовать до конца, вы успешно найдете ключевое слово, в противном случае вы продолжите проходить. Тогда структура ключевых слов должна быть похожа на следующее:
var Keywords = {m: {i: {k: {e: {end: true}}}}, a: {r: {k: {end: true}}}}}Из вышесказанного мы видим, что эти данные являются структурой дерева, и все еще требует много времени создавать структуру дерева, основанную на группе ключевых слов, в то время как ключевые слова уже даются, поэтому вы можете заранее создать такую структуру данных. Код заключается в следующем:
функция BuildTree (Keywords) {var tblcur = {}, ключ, str_key, длина, J, i; var tblroot = tblcur; for (j = ключевые слова. Length = str_key.length; for (i = 0; i <length; i += 1) {key = str_key.charat (i); if (tblcur.hashownproperty (key)) {tblcur = tblcur [key]; } else {tblcur = tblcur [key] = {}; }} tblcur.end = true; // последнее ключевое слово TBLCUR = TBLROOT; } return tblroot;}В этом коде используется непрерывное утверждение: tblcur = tblcur [key] = {}. Заказ о выполнении здесь - это порядок выполнения операторов. Поскольку уровень работы [] выше, чем =, первое, что это создать атрибут ключа в объекте TBLCUR. В сочетании с TBLROOT = TBLCUR = {}, порядок выполнения:
var tblroot = tblcur = {}; tblroot = tblcur; tblcur ['key'] = undefined; // теперь tblroot = {key: undefined} tblcur ['key'] = {}; tblcur = tblcur ['key'];Через приведенный выше код построены требуемые данные запроса. Давайте посмотрим на метод написания интерфейса запроса.
Для каждого слова целевой строки мы начинаем с верхней части этих ключевых слов. Во -первых, ключевые слова [A]. Если есть, посмотрите на ключевое слово [a] [b]. Если последнее ключевое слово [a] [b]… [x] = true, это означает, что совпадение успешно. Если ключевое слово [a] [b]… [x] = не определено, то сопоставление будет перезагружено с следующей позиции.
function search (content) {var tblcur, p_star = 0, n = content.length, p_end, match, // Найти Match_key, match_str, arrmatch = [], // result arrlength = 0; // Индекс длины Armatch while (p_star <n) {tblcur = tblroot; // отслеживание обратно в корень p_end = p_star; match_str = ""; match = false; do {match_key = content.charat (p_end); if (! (tblcur = tblcur [match_key])) {// конец этого совпадения p_star += 1; перерыв; } else {match_str += match_key; } p_end += 1; if (tblcur.end) // соответствует ли хвост {match = true; }} while (true); if (match) {// makemum match arrmatch [arrlength] = {key: match_str, begin: p_star - 1, end: p_end}; arrlength += 1; p_star = p_end; }} return arrmatch;}Выше приведено ядро всей системы сопоставления ключевых слов. Здесь мы очень хорошо используем языковые особенности JS, и эффективность очень высока. Я использовал 500 000 слов «Soushen Ji», чтобы проверить его, и нашел данные 300 идиомы. Соответствующий эффект составляет около 1 секунды. Важно отметить, что, поскольку целевой текст проходит сразу, длина целевого текста мало влияет на время запроса. Количество ключевых слов, которые оказывают большее влияние на время запроса, - это количество ключевых слов. Каждое слово в целевом тексте пересекает ключевые слова, поэтому оно оказывает определенное влияние на запрос.
Простой анализ
Я думаю, вам интересно, когда вы прочитаете вышеуказанную статью. Вы можете пройти все ключевые слова для каждого слова. Даже если некоторые ключевые слова частично одинаковы, это довольно много времени, чтобы полностью пройти их полностью. Однако свойства объектов в JS построены с использованием хэш -таблицы. Данные этой структуры сильно отличаются от простых обновлений массива, и эффективность намного выше, чем у пересадки массива на основе порядка. Некоторые студенты могут не быть знакомы со структурами данных, поэтому я кратко расскажу о соответствующем содержании хэш -таблицы.
Во -первых, давайте посмотрим на хранение данных.
Хранение данных в памяти состоит из двух частей, одна - это значение, а другая - адрес. Думайте о памяти как о словаре Синьхуа, объяснение слова - это значение, а каталог - это адрес. Словарь сортируется с Pinyin, например: «Ni» с тем же произношением расположено в той же части, то есть массив аккуратно расположен в области памяти. Эта структура является массивом, вы можете указать «Ni» номер 1 и 10, чтобы получить к нему доступ. Структурная диаграмма выглядит следующим образом:
Преимущество массивов состоит в том, что они просты в прохождении, и они могут напрямую получить доступ к соответствующим данным с помощью подписок. Но очень трудно добавить или удалить определенный элемент. Например, если вы хотите удалить элемент 6, то данные после элемента 5 должны быть перемещены вперед на одну позицию. Если вы хотите удалить первый бит, весь массив должен быть перенесен, что много потребляет.
Чтобы решить проблему сложения и удаления массива, появляются связанные списки. Если мы разделяем значение на две части, часть используется для хранения исходного значения, а другая часть используется для хранения адреса, которая указывает на другую и ту же структуру, и т. Д., Сформировать связанный список. Структура заключается в следующем:
Из приведенного выше показателя можно ясно увидеть, что добавление и удаление связанного списка очень проста. Просто переписывайте целевой элемент и следующий элемент предыдущего элемента, и он будет завершен. Тем не менее, очень трудно запросить значение элемента. Вы должны пройти его, чтобы получить доступ к целевому местоположению.
Чтобы интегрировать преимущества этих двух структур, вы должны подумать о следующей структуре.
Эта структура данных представляет собой хэш -структуру. Адрес заголовка связанного списка хранится в массиве, и можно сформировать двухмерную таблицу данных. Что касается того, как распространяются данные, это алгоритм хэширования, и регулярный перевод должен быть алгоритмом хэширования. Хотя существует много типов алгоритмов, в принципе они решают ключ через функцию, а затем размещают данные в соответствии с результатами, полученными из решения. Другими словами, между ключом и фактическим адресом формируется отображение, поэтому в настоящее время мы больше не получаем доступа к массиву, подписывая массив или просто пройдя его, но вместо этого находим данные по обратной функции функции хэш. Объект в JS - хэш -структура. Например, мы определяем OBJ. Obj.same через хешинг, и его положение в памяти может быть 90 на рисунке выше. Когда мы хотим управлять obj.name, базовый уровень автоматически поможет нам найти положение 90 через алгоритм хэш, что означает, что мы напрямую начинаем искать связанный список из 12 элементов массива, а не пересекать весь блок памяти от 0.
Определите объект obj {key: value} в JS. Ключ преобразуется в строку, а затем хэшируется для получения адреса памяти, а затем поместите в нее значение. Это позволяет нам понять, почему мы можем добавлять и удалять атрибуты по желанию, и почему мы также можем назначить атрибуты массивам в JS, и не существует так называемого трансграничного массива.
В ситуациях, когда объем данных велик, хэш -таблица имеет очень очевидное преимущество, потому что она снижает много ненужных расчетов с помощью алгоритма хэш. Так называемая оптимизация производительности на самом деле заключается в том, чтобы сделать компьютеры меньше вычислений; Самая большая оптимизация - не рассчитывать!
Оптимизация алгоритмов
Теперь, когда вы понимаете основную реализацию алгоритма, вы можете рассмотреть возможность оптимизации алгоритма в ретроспективе. Однако, прежде чем оптимизировать, вы должны подчеркнуть одну вещь: не слепо не занимайтесь производительностью! Например, в этом случае мы можем соответствовать 5000 слов, поэтому существующий алгоритм достаточно, и всех оптимизаций не нужны. Причина, по которой я все еще говорю об оптимизации, состоит в том, чтобы улучшить мое понимание алгоритма и программы, а не делать оптимизацию 1 мс.
Мы обнаружили, что ни одно из наших ключевых слов не имеет ни одного слова, поэтому для нас было бы пустой травой, чтобы пройти ключевые слова в соответствии с единицей одного слова. Оптимизация здесь состоит в том, чтобы предварительно статистить максимальную и минимальную длину ключевого слова и каждый раз искать в единицах минимальной длины. Например, ключевое слово в моем тестовом примере - идиома, и самым коротким является 4 символа, поэтому каждый раз, когда я совпадаю, я совмещаю 4 символа вместе. Если я нажму, продолжайте искать глубину, чтобы найти максимальную длину. Другими словами, когда мы сначала строим дерево, оно сначала построено с минимальной длиной, а затем добавляется дословно.
Простой расчет сделан. Согласно нашему тестируемому примеру, для 300 идиомов нам нужно сравнить только одно слово только один раз, и для запроса в один слов нам необходимо сравнить 4 раза, и каждое сравнение мы должны получить доступ к нашей структуре деревьев, которая представляет собой потребление производительности. Что еще более важно, сравнение здесь не является сравнением строк. Наши ключевые слова здесь существуют в виде ключей, и эффект такой же, как и ключ в OBJ, который имеет ключ, а затем доступ к соответствующему адресу! Так что не беспокойтесь о разнице между сравнением одного слова и сравнением четырех слов. Мы не сравнивали струны!
Это все о сопоставлении нескольких ключевых слов. Я не буду публиковать оптимизированную версию кода, потому что он обычно недоступен.