You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@texera.apache.org by "chenlica (via GitHub)" <gi...@apache.org> on 2025/10/20 05:42:22 UTC
[D] Aho Corasick String Matching Algorithm [texera]
GitHub user chenlica created a discussion: Aho Corasick String Matching Algorithm
This discussion saved the content of the old wiki page https://github.com/apache/texera/wiki/Aho-Corasick-String-Matching-Algorithm
==========
Aho-Corasick Algorithm is a dictionary-matching algorithm to output all matched dictionary entries with a single pass on the input text.
Wiki Page: https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm
The linear time complexity can help to speed up the process of dictionary matcher on substring matching type.
Given all the dictionary entries as the input, Dictionary Matcher firstly preprocess them to construct an automaton once and save for later data stream to match.
The automaton starts with a prefix trie of all the words to be matched.
Then three main functions including success transactions, failure transactions and output matching words for each trie node will be set up using bread first search traversal on the trie:
The success transactions follows the edges in the trie to find the children of current trie node.
The failure transactions set up links between failed string matches and the nodes on other branches which share the longest common suffix.
The output list stores all the words ending at current node and its failure node.
When executing on the input text, the algorithm traverse the graph by firstly following the success transactions to the child node, if it doesn't exist, then following the failure transactions to its proper suffix node.
When the algorithm reaches a node with a non-empty output keyword list, it outputs all the matched dictionary entires that ends at current character position in the input text.
GitHub link: https://github.com/apache/texera/discussions/3951
----
This is an automatically sent email for notifications@texera.apache.org.
To unsubscribe, please send an email to: notifications-unsubscribe@texera.apache.org
Re: [D] Aho Corasick String Matching Algorithm [texera]
Posted by "chenlica (via GitHub)" <gi...@apache.org>.
GitHub user chenlica added a comment to the discussion: Aho Corasick String Matching Algorithm
Good. That's the plan.
GitHub link: https://github.com/apache/texera/discussions/3951#discussioncomment-14725751
----
This is an automatically sent email for notifications@texera.apache.org.
To unsubscribe, please send an email to: notifications-unsubscribe@texera.apache.org
Re: [D] Aho Corasick String Matching Algorithm [texera]
Posted by "chenlica (via GitHub)" <gi...@apache.org>.
GitHub user chenlica edited a discussion: Aho Corasick String Matching Algorithm
This discussion saved the content of the old wiki page https://github.com/apache/texera/wiki/Aho-Corasick-String-Matching-Algorithm (may be dangling).
==========
Aho-Corasick Algorithm is a dictionary-matching algorithm to output all matched dictionary entries with a single pass on the input text.
Wiki Page: https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm
The linear time complexity can help to speed up the process of dictionary matcher on substring matching type.
Given all the dictionary entries as the input, Dictionary Matcher firstly preprocess them to construct an automaton once and save for later data stream to match.
The automaton starts with a prefix trie of all the words to be matched.
Then three main functions including success transactions, failure transactions and output matching words for each trie node will be set up using bread first search traversal on the trie:
The success transactions follows the edges in the trie to find the children of current trie node.
The failure transactions set up links between failed string matches and the nodes on other branches which share the longest common suffix.
The output list stores all the words ending at current node and its failure node.
When executing on the input text, the algorithm traverse the graph by firstly following the success transactions to the child node, if it doesn't exist, then following the failure transactions to its proper suffix node.
When the algorithm reaches a node with a non-empty output keyword list, it outputs all the matched dictionary entires that ends at current character position in the input text.
GitHub link: https://github.com/apache/texera/discussions/3951
----
This is an automatically sent email for notifications@texera.apache.org.
To unsubscribe, please send an email to: notifications-unsubscribe@texera.apache.org
Re: [D] Aho Corasick String Matching Algorithm [texera]
Posted by "chenlica (via GitHub)" <gi...@apache.org>.
GitHub user chenlica closed a discussion: Aho Corasick String Matching Algorithm
This discussion saved the content of the old wiki page https://github.com/apache/texera/wiki/Aho-Corasick-String-Matching-Algorithm (may be dangling).
==========
Aho-Corasick Algorithm is a dictionary-matching algorithm to output all matched dictionary entries with a single pass on the input text.
Wiki Page: https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm
The linear time complexity can help to speed up the process of dictionary matcher on substring matching type.
Given all the dictionary entries as the input, Dictionary Matcher firstly preprocess them to construct an automaton once and save for later data stream to match.
The automaton starts with a prefix trie of all the words to be matched.
Then three main functions including success transactions, failure transactions and output matching words for each trie node will be set up using bread first search traversal on the trie:
The success transactions follows the edges in the trie to find the children of current trie node.
The failure transactions set up links between failed string matches and the nodes on other branches which share the longest common suffix.
The output list stores all the words ending at current node and its failure node.
When executing on the input text, the algorithm traverse the graph by firstly following the success transactions to the child node, if it doesn't exist, then following the failure transactions to its proper suffix node.
When the algorithm reaches a node with a non-empty output keyword list, it outputs all the matched dictionary entires that ends at current character position in the input text.
GitHub link: https://github.com/apache/texera/discussions/3951
----
This is an automatically sent email for notifications@texera.apache.org.
To unsubscribe, please send an email to: notifications-unsubscribe@texera.apache.org
Re: [D] Aho Corasick String Matching Algorithm [texera]
Posted by "Yicong-Huang (via GitHub)" <gi...@apache.org>.
GitHub user Yicong-Huang added a comment to the discussion: Aho Corasick String Matching Algorithm
do you want to remove the reference link? as we plan to remove the targeted wiki, the link will be dangling.
GitHub link: https://github.com/apache/texera/discussions/3951#discussioncomment-14725729
----
This is an automatically sent email for notifications@texera.apache.org.
To unsubscribe, please send an email to: notifications-unsubscribe@texera.apache.org
Re: [D] Aho Corasick String Matching Algorithm [texera]
Posted by "chenlica (via GitHub)" <gi...@apache.org>.
GitHub user chenlica added a comment to the discussion: Aho Corasick String Matching Algorithm
For archiving purposes, it's better to keep the link. I added "(may be dangling)". Please check.
GitHub link: https://github.com/apache/texera/discussions/3951#discussioncomment-14725744
----
This is an automatically sent email for notifications@texera.apache.org.
To unsubscribe, please send an email to: notifications-unsubscribe@texera.apache.org
Re: [D] Aho Corasick String Matching Algorithm [texera]
Posted by "chenlica (via GitHub)" <gi...@apache.org>.
GitHub user chenlica edited a discussion: Aho Corasick String Matching Algorithm
This discussion saved the content of the old wiki page https://github.com/apache/texera/wiki/Aho-Corasick-String-Matching-Algorithm (may be deleted).
==========
Aho-Corasick Algorithm is a dictionary-matching algorithm to output all matched dictionary entries with a single pass on the input text.
Wiki Page: https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm
The linear time complexity can help to speed up the process of dictionary matcher on substring matching type.
Given all the dictionary entries as the input, Dictionary Matcher firstly preprocess them to construct an automaton once and save for later data stream to match.
The automaton starts with a prefix trie of all the words to be matched.
Then three main functions including success transactions, failure transactions and output matching words for each trie node will be set up using bread first search traversal on the trie:
The success transactions follows the edges in the trie to find the children of current trie node.
The failure transactions set up links between failed string matches and the nodes on other branches which share the longest common suffix.
The output list stores all the words ending at current node and its failure node.
When executing on the input text, the algorithm traverse the graph by firstly following the success transactions to the child node, if it doesn't exist, then following the failure transactions to its proper suffix node.
When the algorithm reaches a node with a non-empty output keyword list, it outputs all the matched dictionary entires that ends at current character position in the input text.
GitHub link: https://github.com/apache/texera/discussions/3951
----
This is an automatically sent email for notifications@texera.apache.org.
To unsubscribe, please send an email to: notifications-unsubscribe@texera.apache.org
Re: [D] Aho Corasick String Matching Algorithm [texera]
Posted by "Yicong-Huang (via GitHub)" <gi...@apache.org>.
GitHub user Yicong-Huang added a comment to the discussion: Aho Corasick String Matching Algorithm
sounds good
GitHub link: https://github.com/apache/texera/discussions/3951#discussioncomment-14725748
----
This is an automatically sent email for notifications@texera.apache.org.
To unsubscribe, please send an email to: notifications-unsubscribe@texera.apache.org