Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Bitap_algorithm> ?p ?o }
Showing triples 1 to 64 of
64
with 100 triples per page.
- Bitap_algorithm abstract "The bitap algorithm (also known as the shift-or, shift-and or Baeza-Yates–Gonnet algorithm) is an approximate string matching algorithm. The algorithm tells whether a given text contains a substring which is "approximately equal" to a given pattern, where approximate equality is defined in terms of Levenshtein distance — if the substring and pattern are within a given distance k of each other, then the algorithm considers them equal. The algorithm begins by precomputing a set of bitmasks containing one bit for each element of the pattern. Then it is able to do most of the work with bitwise operations, which are extremely fast.The bitap algorithm is perhaps best known as one of the underlying algorithms of the Unix utility agrep, written by Udi Manber, Sun Wu, and Burra Gopal. Manber and Wu's original paper gives extensions of the algorithm to deal with fuzzy matching of general regular expressions.Due to the data structures required by the algorithm, it performs best on patterns less than a constant length (typically the word length of the machine in question), and also prefers inputs over a small alphabet. Once it has been implemented for a given alphabet and word length m, however, its running time is completely predictable — it runs in O(mn) operations, no matter the structure of the text or the pattern.The bitap algorithm for exact string searching was invented by Bálint Dömölki in 1964 and extended by R. K. Shyamasundar in 1977, before being reinvented in the context of fuzzy string searching by Manber and Wu in 1991 based on work done by Ricardo Baeza-Yates and Gaston Gonnet. The algorithm was improved by Baeza-Yates and Navarro in 1996 and later by Gene Myers for long patterns in 1998.".
- Bitap_algorithm wikiPageExternalLink libbitap.html.
- Bitap_algorithm wikiPageExternalLink bitap.py.
- Bitap_algorithm wikiPageID "2242223".
- Bitap_algorithm wikiPageLength "8897".
- Bitap_algorithm wikiPageOutDegree "29".
- Bitap_algorithm wikiPageRevisionID "673760550".
- Bitap_algorithm wikiPageWikiLink Agrep.
- Bitap_algorithm wikiPageWikiLink Approximate_string_matching.
- Bitap_algorithm wikiPageWikiLink Big_O_notation.
- Bitap_algorithm wikiPageWikiLink Bitmask.
- Bitap_algorithm wikiPageWikiLink Bitwise_operation.
- Bitap_algorithm wikiPageWikiLink Burra_Gopal.
- Bitap_algorithm wikiPageWikiLink Category:Articles_with_example_C_code.
- Bitap_algorithm wikiPageWikiLink Category:String_matching_algorithms.
- Bitap_algorithm wikiPageWikiLink Communications_of_the_ACM.
- Bitap_algorithm wikiPageWikiLink Eugene_Myers.
- Bitap_algorithm wikiPageWikiLink Fuzzy_matching.
- Bitap_algorithm wikiPageWikiLink Gaston_Gonnet.
- Bitap_algorithm wikiPageWikiLink Gene_Myers.
- Bitap_algorithm wikiPageWikiLink Gonzalo_Navarro.
- Bitap_algorithm wikiPageWikiLink Hamming_distance.
- Bitap_algorithm wikiPageWikiLink Inner_loop.
- Bitap_algorithm wikiPageWikiLink Levenshtein_distance.
- Bitap_algorithm wikiPageWikiLink Mask_(computing).
- Bitap_algorithm wikiPageWikiLink Programming_tool.
- Bitap_algorithm wikiPageWikiLink Record_linkage.
- Bitap_algorithm wikiPageWikiLink Regular_expression.
- Bitap_algorithm wikiPageWikiLink Ricardo_Baeza-Yates.
- Bitap_algorithm wikiPageWikiLink Running_time.
- Bitap_algorithm wikiPageWikiLink String_searching_algorithm.
- Bitap_algorithm wikiPageWikiLink Sun_Wu_(computer_scientist).
- Bitap_algorithm wikiPageWikiLink Time_complexity.
- Bitap_algorithm wikiPageWikiLink Udi_Manber.
- Bitap_algorithm wikiPageWikiLink University_of_Arizona.
- Bitap_algorithm wikiPageWikiLink Unix.
- Bitap_algorithm wikiPageWikiLink Word_(computer_architecture).
- Bitap_algorithm wikiPageWikiLink Word_length.
- Bitap_algorithm wikiPageWikiLinkText "Bitap algorithm".
- Bitap_algorithm wikiPageWikiLinkText "Bitap_algorithm".
- Bitap_algorithm wikiPageWikiLinkText "bitap algorithm".
- Bitap_algorithm hasPhotoCollection Bitap_algorithm.
- Bitap_algorithm wikiPageUsesTemplate Template:Doi.
- Bitap_algorithm wikiPageUsesTemplate Template:Note.
- Bitap_algorithm wikiPageUsesTemplate Template:Ref.
- Bitap_algorithm subject Category:Articles_with_example_C_code.
- Bitap_algorithm subject Category:String_matching_algorithms.
- Bitap_algorithm hypernym String.
- Bitap_algorithm type Article.
- Bitap_algorithm type Island.
- Bitap_algorithm type Algorithm.
- Bitap_algorithm type Article.
- Bitap_algorithm comment "The bitap algorithm (also known as the shift-or, shift-and or Baeza-Yates–Gonnet algorithm) is an approximate string matching algorithm. The algorithm tells whether a given text contains a substring which is "approximately equal" to a given pattern, where approximate equality is defined in terms of Levenshtein distance — if the substring and pattern are within a given distance k of each other, then the algorithm considers them equal.".
- Bitap_algorithm label "Bitap algorithm".
- Bitap_algorithm sameAs Baeza-Yates-Gonnet-Algorithmus.
- Bitap_algorithm sameAs الگوریتم_بایتپ.
- Bitap_algorithm sameAs Algorithme_de_Baeza-Yates-Gonnet.
- Bitap_algorithm sameAs Bitapアルゴリズム.
- Bitap_algorithm sameAs m.06ymll.
- Bitap_algorithm sameAs Двоичный_алгоритм_поиска_подстроки.
- Bitap_algorithm sameAs Q446273.
- Bitap_algorithm sameAs Q446273.
- Bitap_algorithm wasDerivedFrom Bitap_algorithm?oldid=673760550.
- Bitap_algorithm isPrimaryTopicOf Bitap_algorithm.