About: Aho–Corasick algorithm

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Aho–Corasick algorithm Goto Sponge NotDistinct Permalink

An Entity of Type : dbo:Island, within Data Space : el.dbpedia.org associated with source document(s)

In computer science, the Aho–Corasick algorithm is a string-searching algorithm invented by Alfred V. Aho and Margaret J. Corasick in 1975. 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 strings simultaneously. The complexity of the algorithm is linear in the length of the strings 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).

Attributes	Values
rdf:type	island
rdfs:label	Aho–Corasick algorithm (en)
rdfs:comment	In computer science, the Aho–Corasick algorithm is a string-searching algorithm invented by Alfred V. Aho and Margaret J. Corasick in 1975. 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 strings simultaneously. The complexity of the algorithm is linear in the length of the strings 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). (en)
sameAs	Aho–Corasick algorithm
dbp:wikiPageUsesTemplate	dbt:Clear dbt:Commonscat dbt:Mono dbt:Reflist dbt:GitHub dbt:Github dbt:Strings
Subject	String matching algorithms
Link from a Wikipage to an external page	https://wiomoc.de/aho-corasick-viz/ https://xlinux.nist.gov/dads/HTML/ahoCorasick.html
thumbnail	wiki-commons:Special:FilePath/Ahocorasick.svg?width=300
foaf:depiction
gold:hypernym	String
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Aho–Corasick_algorithm?oldid=1056720115&ns=0
Wikipage page ID	184607 (xsd:integer)
page length (characters) of wiki page	8005 (xsd:nonNegativeInteger)
Wikipage revision ID	1056720115 (xsd:integer)
Link from a Wikipage to another Wikipage	Grep List of terms relating to algorithms and data structures Alfred Aho Bertrand Meyer Breadth-first search String matching algorithms Time complexity Trie Commentz-Walter algorithm Computer science Computer virus List of Unix commands Finite-state machine String-searching algorithm Memoization
has abstract	In computer science, the Aho–Corasick algorithm is a string-searching algorithm invented by Alfred V. Aho and Margaret J. Corasick in 1975. 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 strings simultaneously. The complexity of the algorithm is linear in the length of the strings 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 string 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 string matches without the need for backtracking. When the string 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. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Aho–Corasick_algorithm
is Wikipage redirect of	Aho-Corasick algorithm Aho-Corasick string matching algorithm Aho–Corasick string matching algorithm Aho-Corasick Margaret J. Corasick
is Link from a Wikipage to another Wikipage of	Grep Aho-Corasick algorithm Aho-Corasick string matching algorithm Aho–Corasick string matching algorithm Alfred Aho Breadth-first search Commentz-Walter algorithm Edit distance List of algorithms Index of combinatorics articles Aho-Corasick Margaret J. Corasick
is known for of	Alfred Aho
is foaf:primaryTopic of	http://en.wikipedia.org/wiki/Aho–Corasick_algorithm

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (71 GB total memory, 2 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software