Я записал простую функцию, которая определяет, является ли строка str1 префиксом строки str2. Это очень простая функция, которая выглядит так (в JS):
function isPrefix(str1, str2) // determine if str1 is a prefix of a candidate string
{
if(str2.length < str1.length) // candidate string can't be smaller than prefix string
return false;
var i = 0;
while(str1.charAt(i) == str2.charAt(i) && i <= str1.length)
i++;
if(i < str1.length) // i terminated => str 1 is smaller than str 2
return false;
return true;
}
Как видите, он перебирает всю длину строки префикса, чтобы определить, является ли она префиксом строки-кандидата. Это означает, что его сложность равна O(N), что неплохо, но это становится проблемой, когда у меня есть огромный набор данных, чтобы рассмотреть цикл, чтобы определить, какие строки имеют строку префикса как часть префикса. Это делает сложность кратной, как O (M * N), где M — общее количество строк в данном наборе данных. Фигово.
Я немного изучил Интернет, чтобы определить, что лучшим ответом будет тройка Patricia/Radix. Где строки хранятся как префиксы. Даже тогда, когда я пытаюсь вставить/поиск строки, будут значительные накладные расходы на сопоставление строк, если я использую вышеупомянутую функцию проверки префикса.
Скажем, у меня была строка префикса «rom» и набор слов-кандидатов.
var dataset =["случайный","быстрый","романтика","румыния","рим","роза"];
что хотело бы это в radix trie :
r
/ \
a o
/ \ / \
ndom pid se m
/ \
an e
/ \
ia ce
Это означает, что для каждого узла я буду использовать функцию сопоставления префикса, чтобы определить, какой узел имеет значение, соответствующее строке префикса в индексе. Почему-то это решение все еще кажется трудным и не слишком мне подходит. Есть ли что-то лучше или в любом случае я могу улучшить функцию сопоставления основных префиксов?
