What is an efficient data structure for prefix matching?
$begingroup$
I'm looking for an data structure that supports efficient random prefix matching queries (pattern) over a previously known set of words (dictionary). The dictionary is expected to contain about 10,000 words of varying length (I haven't calculated average word length, but I don't expect any word to be more than 80 characters long). Prefix matching in this case would be equivalent to words[i].toLowerCase().startsWith(pattern.toLowerCase()).
A Trie is an obvious choice, and provides linear time search corresponding to the length of the pattern. However, I'm confused whether a Suffix Tree, or a Suffix Array, might provide any improvements over a Trie. It seems a Suffix whatever is commonly used for one text, not multiple. I also have no requirement for supporting the various cool use cases (longest common prefix, or number of times a prefix occurs etc) that Suffix whatever can efficiently support.
I'm looking for a recommendation on which data structure to use, and why. Tries use a lot of space, and if I end up using one, I'd consider compress the branches with nodes with outdegree 1.
For the duplicate button happy readers, I've read this and this question, none seemed directly relevant.
Example:
Dictionary: [banana, apple, banter, orange]
Pattern: ban
Return: banana (any match)
Pattern: grapes
Return: null
data-structures search-algorithms strings substrings
asked 6 hours ago
Abhijit SarkarAbhijit Sarkar
17913
$endgroup$
add a comment |
$begingroup$
I'm looking for an data structure that supports efficient random prefix matching queries (pattern) over a previously known set of words (dictionary). The dictionary is expected to contain about 10,000 words of varying length (I haven't calculated average word length, but I don't expect any word to be more than 80 characters long). Prefix matching in this case would be equivalent to words[i].toLowerCase().startsWith(pattern.toLowerCase()).
A Trie is an obvious choice, and provides linear time search corresponding to the length of the pattern. However, I'm confused whether a Suffix Tree, or a Suffix Array, might provide any improvements over a Trie. It seems a Suffix whatever is commonly used for one text, not multiple. I also have no requirement for supporting the various cool use cases (longest common prefix, or number of times a prefix occurs etc) that Suffix whatever can efficiently support.
I'm looking for a recommendation on which data structure to use, and why. Tries use a lot of space, and if I end up using one, I'd consider compress the branches with nodes with outdegree 1.
For the duplicate button happy readers, I've read this and this question, none seemed directly relevant.
Example:
Dictionary: [banana, apple, banter, orange]
Pattern: ban
Return: banana (any match)
Pattern: grapes
Return: null
data-structures search-algorithms strings substrings
asked 6 hours ago
Abhijit SarkarAbhijit Sarkar
17913
$endgroup$
2
$begingroup$
What does "prefix matching queries (pattern)" mean? Can you specify the operation that you want to perform on the data structure more carefully?
$endgroup$
– D.W.♦
5 hours ago
$begingroup$
Why "ban" pattern does not yield "banana" and "banter"? What pattern **"e" **returns in your case?
$endgroup$
– Evil
5 hours ago
1
$begingroup$
@Evil It's specified already in my example, any match, assuming "banana" is the path the code chose. "banter" would be a perfectly acceptable answer too.
$endgroup$
– Abhijit Sarkar
5 hours ago
$begingroup$
@D.W. I thought it was plenty obvious what prefix match means, but I've updated my question with a code snippet to demonstrate it explicitly.
$endgroup$
– Abhijit Sarkar
5 hours ago
add a comment |
$begingroup$
I'm looking for an data structure that supports efficient random prefix matching queries (pattern) over a previously known set of words (dictionary). The dictionary is expected to contain about 10,000 words of varying length (I haven't calculated average word length, but I don't expect any word to be more than 80 characters long). Prefix matching in this case would be equivalent to words[i].toLowerCase().startsWith(pattern.toLowerCase()).
A Trie is an obvious choice, and provides linear time search corresponding to the length of the pattern. However, I'm confused whether a Suffix Tree, or a Suffix Array, might provide any improvements over a Trie. It seems a Suffix whatever is commonly used for one text, not multiple. I also have no requirement for supporting the various cool use cases (longest common prefix, or number of times a prefix occurs etc) that Suffix whatever can efficiently support.
I'm looking for a recommendation on which data structure to use, and why. Tries use a lot of space, and if I end up using one, I'd consider compress the branches with nodes with outdegree 1.
For the duplicate button happy readers, I've read this and this question, none seemed directly relevant.
Example:
Dictionary: [banana, apple, banter, orange]
Pattern: ban
Return: banana (any match)
Pattern: grapes
Return: null
data-structures search-algorithms strings substrings
asked 6 hours ago
Abhijit SarkarAbhijit Sarkar
17913
$endgroup$
I'm looking for an data structure that supports efficient random prefix matching queries (pattern) over a previously known set of words (dictionary). The dictionary is expected to contain about 10,000 words of varying length (I haven't calculated average word length, but I don't expect any word to be more than 80 characters long). Prefix matching in this case would be equivalent to words[i].toLowerCase().startsWith(pattern.toLowerCase()).
A Trie is an obvious choice, and provides linear time search corresponding to the length of the pattern. However, I'm confused whether a Suffix Tree, or a Suffix Array, might provide any improvements over a Trie. It seems a Suffix whatever is commonly used for one text, not multiple. I also have no requirement for supporting the various cool use cases (longest common prefix, or number of times a prefix occurs etc) that Suffix whatever can efficiently support.
I'm looking for a recommendation on which data structure to use, and why. Tries use a lot of space, and if I end up using one, I'd consider compress the branches with nodes with outdegree 1.
For the duplicate button happy readers, I've read this and this question, none seemed directly relevant.
Example:
Dictionary: [banana, apple, banter, orange]
Pattern: ban
Return: banana (any match)
Pattern: grapes
Return: null
data-structures search-algorithms strings substrings
data-structures search-algorithms strings substrings
asked 6 hours ago
Abhijit SarkarAbhijit Sarkar
17913
asked 6 hours ago
Abhijit SarkarAbhijit Sarkar
17913
edited 5 hours ago
Abhijit Sarkar
asked 6 hours ago
Abhijit SarkarAbhijit Sarkar
17913
asked 6 hours ago
Abhijit SarkarAbhijit Sarkar
17913
asked 6 hours ago
Abhijit SarkarAbhijit Sarkar
17913
17913
2
$begingroup$
What does "prefix matching queries (pattern)" mean? Can you specify the operation that you want to perform on the data structure more carefully?
$endgroup$
– D.W.♦
5 hours ago
$begingroup$
Why "ban" pattern does not yield "banana" and "banter"? What pattern **"e" **returns in your case?
$endgroup$
– Evil
5 hours ago
1
$begingroup$
@Evil It's specified already in my example, any match, assuming "banana" is the path the code chose. "banter" would be a perfectly acceptable answer too.
$endgroup$
– Abhijit Sarkar
5 hours ago
$begingroup$
@D.W. I thought it was plenty obvious what prefix match means, but I've updated my question with a code snippet to demonstrate it explicitly.
$endgroup$
– Abhijit Sarkar
5 hours ago
add a comment |
2
$begingroup$
What does "prefix matching queries (pattern)" mean? Can you specify the operation that you want to perform on the data structure more carefully?
$endgroup$
– D.W.♦
5 hours ago
$begingroup$
Why "ban" pattern does not yield "banana" and "banter"? What pattern **"e" **returns in your case?
$endgroup$
– Evil
5 hours ago
1
$begingroup$
@Evil It's specified already in my example, any match, assuming "banana" is the path the code chose. "banter" would be a perfectly acceptable answer too.
$endgroup$
– Abhijit Sarkar
5 hours ago
$begingroup$
@D.W. I thought it was plenty obvious what prefix match means, but I've updated my question with a code snippet to demonstrate it explicitly.
$endgroup$
– Abhijit Sarkar
5 hours ago
2
2
$begingroup$
What does "prefix matching queries (pattern)" mean? Can you specify the operation that you want to perform on the data structure more carefully?
$endgroup$
– D.W.♦
5 hours ago
$begingroup$
What does "prefix matching queries (pattern)" mean? Can you specify the operation that you want to perform on the data structure more carefully?
$endgroup$
– D.W.♦
5 hours ago
$begingroup$
Why "ban" pattern does not yield "banana" and "banter"? What pattern **"e" **returns in your case?
$endgroup$
– Evil
5 hours ago
$begingroup$
Why "ban" pattern does not yield "banana" and "banter"? What pattern **"e" **returns in your case?
$endgroup$
– Evil
5 hours ago
1
1
$begingroup$
@Evil It's specified already in my example, any match, assuming "banana" is the path the code chose. "banter" would be a perfectly acceptable answer too.
$endgroup$
– Abhijit Sarkar
5 hours ago
$begingroup$
@Evil It's specified already in my example, any match, assuming "banana" is the path the code chose. "banter" would be a perfectly acceptable answer too.
$endgroup$
– Abhijit Sarkar
5 hours ago
$begingroup$
@D.W. I thought it was plenty obvious what prefix match means, but I've updated my question with a code snippet to demonstrate it explicitly.
$endgroup$
– Abhijit Sarkar
5 hours ago
$begingroup$
@D.W. I thought it was plenty obvious what prefix match means, but I've updated my question with a code snippet to demonstrate it explicitly.
$endgroup$
– Abhijit Sarkar
5 hours ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
A trie is asymptotically optimal for this. No data structure can achieve better asymptotic running time.
If you care about constant factors, the only way to know what will be optimal is to try multiple approaches and benchmark them. Standard theoretical running time analysis is not reliable at predicting constant factors.
Another data structure to consider is to store every prefix of each word in a hashtable. This will increase the space usage by about 10x (if the average word length is 10) but might speed up lookups in practice. The asymptotic running time will remain the same. You'll have to decide whether you're willing to trade off space for time.
Suffix trees and suffix arrays don't seem relevant. You're asking about prefix matching, not suffix matching or matching in the middle of the string.
answered 5 hours ago
D.W.♦D.W.
99.5k12121286
$endgroup$
$begingroup$
While I agree with you regarding using Trie, I don't think the claim "Suffix trees and suffix arrays don't seem relevant. You're asking about prefix matching, not suffix matching" holds. One of the most common uses of a suffix tree/array is pattern matching or substring search. See this or this paper.
$endgroup$
– Abhijit Sarkar
4 hours ago
$begingroup$
@AbhijitSarkar, yes, I know how they are used for that; that's for finding an instance of the pattern in the middle of the string. Here you want to anchor the pattern so it is only allowed to occur at the beginning of the string. Suffix trees/arrays don't seem relevant for the latter. (If you think they're useful for that, I suggest trying to work out a specific algorithm for how you would use a suffix tree to help you answer that query, and then maybe you'll see what I mean; or else you'll have some more details you can add to your question to highlight whatever I've overlooked...)
$endgroup$
– D.W.♦
3 hours ago
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f104771%2fwhat-is-an-efficient-data-structure-for-prefix-matching%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
A trie is asymptotically optimal for this. No data structure can achieve better asymptotic running time.
If you care about constant factors, the only way to know what will be optimal is to try multiple approaches and benchmark them. Standard theoretical running time analysis is not reliable at predicting constant factors.
Another data structure to consider is to store every prefix of each word in a hashtable. This will increase the space usage by about 10x (if the average word length is 10) but might speed up lookups in practice. The asymptotic running time will remain the same. You'll have to decide whether you're willing to trade off space for time.
Suffix trees and suffix arrays don't seem relevant. You're asking about prefix matching, not suffix matching or matching in the middle of the string.
answered 5 hours ago
D.W.♦D.W.
99.5k12121286
$endgroup$
$begingroup$
While I agree with you regarding using Trie, I don't think the claim "Suffix trees and suffix arrays don't seem relevant. You're asking about prefix matching, not suffix matching" holds. One of the most common uses of a suffix tree/array is pattern matching or substring search. See this or this paper.
$endgroup$
– Abhijit Sarkar
4 hours ago
$begingroup$
@AbhijitSarkar, yes, I know how they are used for that; that's for finding an instance of the pattern in the middle of the string. Here you want to anchor the pattern so it is only allowed to occur at the beginning of the string. Suffix trees/arrays don't seem relevant for the latter. (If you think they're useful for that, I suggest trying to work out a specific algorithm for how you would use a suffix tree to help you answer that query, and then maybe you'll see what I mean; or else you'll have some more details you can add to your question to highlight whatever I've overlooked...)
$endgroup$
– D.W.♦
3 hours ago
add a comment |
$begingroup$
A trie is asymptotically optimal for this. No data structure can achieve better asymptotic running time.
If you care about constant factors, the only way to know what will be optimal is to try multiple approaches and benchmark them. Standard theoretical running time analysis is not reliable at predicting constant factors.
Another data structure to consider is to store every prefix of each word in a hashtable. This will increase the space usage by about 10x (if the average word length is 10) but might speed up lookups in practice. The asymptotic running time will remain the same. You'll have to decide whether you're willing to trade off space for time.
Suffix trees and suffix arrays don't seem relevant. You're asking about prefix matching, not suffix matching or matching in the middle of the string.
answered 5 hours ago
D.W.♦D.W.
99.5k12121286
$endgroup$
$begingroup$
While I agree with you regarding using Trie, I don't think the claim "Suffix trees and suffix arrays don't seem relevant. You're asking about prefix matching, not suffix matching" holds. One of the most common uses of a suffix tree/array is pattern matching or substring search. See this or this paper.
$endgroup$
– Abhijit Sarkar
4 hours ago
$begingroup$
@AbhijitSarkar, yes, I know how they are used for that; that's for finding an instance of the pattern in the middle of the string. Here you want to anchor the pattern so it is only allowed to occur at the beginning of the string. Suffix trees/arrays don't seem relevant for the latter. (If you think they're useful for that, I suggest trying to work out a specific algorithm for how you would use a suffix tree to help you answer that query, and then maybe you'll see what I mean; or else you'll have some more details you can add to your question to highlight whatever I've overlooked...)
$endgroup$
– D.W.♦
3 hours ago
add a comment |
$begingroup$
A trie is asymptotically optimal for this. No data structure can achieve better asymptotic running time.
If you care about constant factors, the only way to know what will be optimal is to try multiple approaches and benchmark them. Standard theoretical running time analysis is not reliable at predicting constant factors.
Another data structure to consider is to store every prefix of each word in a hashtable. This will increase the space usage by about 10x (if the average word length is 10) but might speed up lookups in practice. The asymptotic running time will remain the same. You'll have to decide whether you're willing to trade off space for time.
Suffix trees and suffix arrays don't seem relevant. You're asking about prefix matching, not suffix matching or matching in the middle of the string.
answered 5 hours ago
D.W.♦D.W.
99.5k12121286
$endgroup$
A trie is asymptotically optimal for this. No data structure can achieve better asymptotic running time.
If you care about constant factors, the only way to know what will be optimal is to try multiple approaches and benchmark them. Standard theoretical running time analysis is not reliable at predicting constant factors.
Another data structure to consider is to store every prefix of each word in a hashtable. This will increase the space usage by about 10x (if the average word length is 10) but might speed up lookups in practice. The asymptotic running time will remain the same. You'll have to decide whether you're willing to trade off space for time.
Suffix trees and suffix arrays don't seem relevant. You're asking about prefix matching, not suffix matching or matching in the middle of the string.
answered 5 hours ago
D.W.♦D.W.
99.5k12121286
edited 3 hours ago
answered 5 hours ago
D.W.♦D.W.
99.5k12121286
answered 5 hours ago
D.W.♦D.W.
99.5k12121286
answered 5 hours ago
D.W.♦D.W.
99.5k12121286
99.5k12121286
$begingroup$
While I agree with you regarding using Trie, I don't think the claim "Suffix trees and suffix arrays don't seem relevant. You're asking about prefix matching, not suffix matching" holds. One of the most common uses of a suffix tree/array is pattern matching or substring search. See this or this paper.
$endgroup$
– Abhijit Sarkar
4 hours ago
$begingroup$
@AbhijitSarkar, yes, I know how they are used for that; that's for finding an instance of the pattern in the middle of the string. Here you want to anchor the pattern so it is only allowed to occur at the beginning of the string. Suffix trees/arrays don't seem relevant for the latter. (If you think they're useful for that, I suggest trying to work out a specific algorithm for how you would use a suffix tree to help you answer that query, and then maybe you'll see what I mean; or else you'll have some more details you can add to your question to highlight whatever I've overlooked...)
$endgroup$
– D.W.♦
3 hours ago
add a comment |
$begingroup$
While I agree with you regarding using Trie, I don't think the claim "Suffix trees and suffix arrays don't seem relevant. You're asking about prefix matching, not suffix matching" holds. One of the most common uses of a suffix tree/array is pattern matching or substring search. See this or this paper.
$endgroup$
– Abhijit Sarkar
4 hours ago
$begingroup$
@AbhijitSarkar, yes, I know how they are used for that; that's for finding an instance of the pattern in the middle of the string. Here you want to anchor the pattern so it is only allowed to occur at the beginning of the string. Suffix trees/arrays don't seem relevant for the latter. (If you think they're useful for that, I suggest trying to work out a specific algorithm for how you would use a suffix tree to help you answer that query, and then maybe you'll see what I mean; or else you'll have some more details you can add to your question to highlight whatever I've overlooked...)
$endgroup$
– D.W.♦
3 hours ago
$begingroup$
While I agree with you regarding using Trie, I don't think the claim "Suffix trees and suffix arrays don't seem relevant. You're asking about prefix matching, not suffix matching" holds. One of the most common uses of a suffix tree/array is pattern matching or substring search. See this or this paper.
$endgroup$
– Abhijit Sarkar
4 hours ago
$begingroup$
While I agree with you regarding using Trie, I don't think the claim "Suffix trees and suffix arrays don't seem relevant. You're asking about prefix matching, not suffix matching" holds. One of the most common uses of a suffix tree/array is pattern matching or substring search. See this or this paper.
$endgroup$
– Abhijit Sarkar
4 hours ago
$begingroup$
@AbhijitSarkar, yes, I know how they are used for that; that's for finding an instance of the pattern in the middle of the string. Here you want to anchor the pattern so it is only allowed to occur at the beginning of the string. Suffix trees/arrays don't seem relevant for the latter. (If you think they're useful for that, I suggest trying to work out a specific algorithm for how you would use a suffix tree to help you answer that query, and then maybe you'll see what I mean; or else you'll have some more details you can add to your question to highlight whatever I've overlooked...)
$endgroup$
– D.W.♦
3 hours ago
$begingroup$
@AbhijitSarkar, yes, I know how they are used for that; that's for finding an instance of the pattern in the middle of the string. Here you want to anchor the pattern so it is only allowed to occur at the beginning of the string. Suffix trees/arrays don't seem relevant for the latter. (If you think they're useful for that, I suggest trying to work out a specific algorithm for how you would use a suffix tree to help you answer that query, and then maybe you'll see what I mean; or else you'll have some more details you can add to your question to highlight whatever I've overlooked...)
$endgroup$
– D.W.♦
3 hours ago
add a comment |
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f104771%2fwhat-is-an-efficient-data-structure-for-prefix-matching%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
$begingroup$
What does "prefix matching queries (pattern)" mean? Can you specify the operation that you want to perform on the data structure more carefully?
$endgroup$
– D.W.♦
5 hours ago
$begingroup$
Why "ban" pattern does not yield "banana" and "banter"? What pattern **"e" **returns in your case?
$endgroup$
– Evil
5 hours ago
1
$begingroup$
@Evil It's specified already in my example, any match, assuming "banana" is the path the code chose. "banter" would be a perfectly acceptable answer too.
$endgroup$
– Abhijit Sarkar
5 hours ago
$begingroup$
@D.W. I thought it was plenty obvious what prefix match means, but I've updated my question with a code snippet to demonstrate it explicitly.
$endgroup$
– Abhijit Sarkar
5 hours ago