Matches in DBpedia 2016-04 for { <http://wikidata.dbpedia.org/resource/Q402342> ?p ?o }
Showing triples 1 to 20 of
20
with 100 triples per page.
- Q402342 subject Q8819520.
- Q402342 abstract "In computer science, the Aho–Corasick algorithm is a string searching algorithm invented by Alfred V. Aho and Margaret J. Corasick. It is a kind of dictionary-matching algorithm that locates elements of a finite set of strings (the "dictionary") within an input text. It matches all patterns simultaneously. The complexity of the algorithm is linear in the length of the patterns plus the length of the searched text plus the number of output matches. Note that because all matches are found, there can be a quadratic number of matches if every substring matches (e.g. dictionary = a, aa, aaa, aaaa and input string is aaaa).Informally, the algorithm constructs a finite state machine that resembles a trie with additional links between the various internal nodes. These extra internal links allow fast transitions between failed pattern matches (e.g. a search for cat in a trie that does not contain cat, but contains cart, and thus would fail at the node prefixed by ca), to other branches of the trie that share a common prefix (e.g., in the previous case, a branch for attribute might be the best lateral transition). This allows the automaton to transition between pattern matches without the need for backtracking. When the pattern dictionary is known in advance (e.g. a computer virus database), the construction of the automaton can be performed once off-line and the compiled automaton stored for later use. In this case, its run time is linear in the length of the input plus the number of matched entries.The Aho–Corasick string matching algorithm formed the basis of the original Unix command fgrep.".
- Q402342 thumbnail Ahocorasick.svg?width=300.
- Q402342 wikiPageExternalLink slides04.pdf.
- Q402342 wikiPageExternalLink ahoCorasick.html.
- Q402342 wikiPageExternalLink aho_corasick.
- Q402342 wikiPageWikiLink Q176452.
- Q402342 wikiPageWikiLink Q205084.
- Q402342 wikiPageWikiLink Q21198.
- Q402342 wikiPageWikiLink Q283302.
- Q402342 wikiPageWikiLink Q374040.
- Q402342 wikiPageWikiLink Q387015.
- Q402342 wikiPageWikiLink Q4423787.
- Q402342 wikiPageWikiLink Q485.
- Q402342 wikiPageWikiLink Q62898.
- Q402342 wikiPageWikiLink Q839478.
- Q402342 wikiPageWikiLink Q8819520.
- Q402342 comment "In computer science, the Aho–Corasick algorithm is a string searching algorithm invented by Alfred V. Aho and Margaret J. Corasick. It is a kind of dictionary-matching algorithm that locates elements of a finite set of strings (the "dictionary") within an input text. It matches all patterns simultaneously. The complexity of the algorithm is linear in the length of the patterns plus the length of the searched text plus the number of output matches.".
- Q402342 label "Aho–Corasick algorithm".
- Q402342 depiction Ahocorasick.svg.
