I'm looking for a way to speed up my naive string matching process:
// Treat this as pseudo code
function find(input: string, prefixes: string[]) {
for (let i = 0; i < prefixes.length; i++) {
const prefix = prefixes[i];
if (input.startsWith(prefix)) {
return prefix;
}
}
return null;
}
const prefixes = [ "Hey", "Hi", "Hola", ... ];
const prefix = find("Hey, I'm Michael", prefixes);
I've looked into some probabilistic data structures like the bloom filter but I couldn't find one that'd fit my needs. This being said, I don't actually care to get the prefix that would have matched neither do I need a 100% guarantee that a match exists. I only need to know if the input does definitely NOT contain any prefix or that it might.
I've also come across an article about a Burst Tries algorithm which as far as I could understand will serve a similar purpose. Frankly, though I'm not deep enough into algorithms to grasp the full implementation details and make sure this is what I'm looking for.
Side note: I assume that 99.95% of the input this function will be getting is not going to match any prefix. Therefore I would like for this to be an optimization step to only process strings that will likely have a prefix I'm looking for.
Any help or suggestions would be very much appreciated :3
If the prefixes are known in advance and can be preprocessed, you might try a trie. Especially if they are going to be as short as 10 characters. That would mean each check is on the order of 10 comparisons. Not sure how much better one could do.
function buildTrie(trie, words){
for (let word of words){
let _trie = trie;
for (let i=0; i<word.length; i++){
const letter = word[i];
_trie[letter] = _trie[letter] || {};
if (i == word.length - 1)
_trie[letter]['leaf'] = true;
_trie = _trie[letter];
}
}
return trie;
}
function find(trie, str, i=0){
const letter = str[i];
if (!trie[letter])
return false;
if (trie[letter]['leaf'])
return true;
return find(trie[letter], str, i + 1);
}
const prefixes = [ "Hey", "Heya", "Hi", "Hola"];
const trie = buildTrie({}, prefixes)
console.log(trie)
console.log(find(trie, "Hey, I'm Michael"));
console.log(find(trie, "Heuy, I'm Michael"));This has no logical difference from the answer by גלעד ברקן, but it displays working with a trie in a quite different code style. (It also uses $ instead of leaf as a terminator; a Symbol would be a good alternative.)
const trie = (words) =>
words .reduce (insertWord, {})
const insertWord = (trie, [c, ...cs]) =>
c ? {...trie, [c]: insertWord (trie [c] || {}, cs)} : {...trie, $: 1}
const hasPrefix = (trie) => ([c, ...cs]) =>
'$' in trie ? true : c ? c in trie && hasPrefix (trie [c]) (cs) : true
const testPrefixes = (prefixes) =>
hasPrefix (trie (prefixes))
const hasGreeting = testPrefixes (["Hey", "Hi", "Hola", "Howdy"])
console .log (hasGreeting ("Hey, I'm Michael"))
console .log (hasGreeting ("Hello, Michael. I'm Michelle"))
console .log (trie ((["Hey", "Hi", "Hola", "Howdy"]))).as-console-wrapper {max-height: 100% !important; top: 0}testPrefixes accepts a list of prefixes and returns a function that will report on whether a string starts with one of those prefixes. It does this by creating a trie and partially applying it to hasPrefix. Internally, the trie is built by folding insertWord over an initial empty object.
Of course this only makes sense if your use-case has prefixes that are reused for multiple calls. If not, I see little better than const testPrefixes = (prefixes) => (word) => prefixes .some ((pfx) => word .startsWith (pfx))
For search for a lot of possible substrings in the string, you can use idea from Rabin-Karp algorithm.
In my program Banmoron I used this algorithm for select malicious requests by search substring. See sources on github.