| dbo: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, , and . 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 by Ricardo Baeza-Yates and Gaston Gonnet in 1989 (one chapter of first author's PhD thesis) which also extended it to handle classes of characters, wildcards, and mismatches. In 1991, it was extended by Manber and to handle also insertions and deletions (full fuzzy string searching). This algorithm was later improved by Baeza-Yates and Navarro in 1996. (en)
- Der Baeza-Yates-Gonnet-Algorithmus bzw. Shift-or-Algorithmus, der auch unter den Namen Shift-and oder Bitap bekannt ist, löst das String-Matching-Problem, indem er einen nichtdeterministischen Automaten simuliert. Unter anderem wird eine Abwandlung dieses Algorithmus bei dem Unix-Tool grep benutzt. Da die Implementierung auf Bit-Operationen zurückgeführt werden kann, ist der Algorithmus alleine von der Ausführung her bereits sehr effizient. Kombiniert man dies mit dem zu Grunde liegenden System (im Preprocessing einmal Schleife über das Muster, während der Suche einmal Schleife über den Text) ergibt sich ein extrem effizienter Algorithmus. (de)
- L'algorithme de Baeza-Yates-Gonnet plus connu sous le nom de Shift-Or ou encore Bitap est un algorithme de recherche de sous-chaîne.Sa version en recherche exacte a été publiée par en 1964 avant d'être adaptée en 1996 par et pour satisfaire une recherche approximative. L'algorithme utilise des opérations bit à bit ce qui lui permet d'atteindre une bonne performance. Cependant une limitation inhérente est que la sous-chaîne ne peut dépasser la taille d'un mot machine. Une autre force de Shift-Or est sa capacité à être facilement adapté pour faire des recherches approximatives. (fr)
- Bitapアルゴリズム（英: Bitap algorithm）とは、ビット演算の並列性を利用した文字列探索アルゴリズムである。Baeza–Yates–Gonnetアルゴリズムや、shift-andアルゴリズム・shift-orアルゴリズムとも呼ばれる（andとorがあるのは、ブール代数の双対性にもとづくバリエーションである）。レーベンシュタイン距離などの編集距離に基づく「似た」文字列を見つけ出すに利用できることが、他の文字列探索アルゴリズムにない特徴である。 (ja)
- Двоичный алгоритм поиска подстроки (также bitap algorithm, shift-or algorithm) — алгоритм поиска подстроки, использующий тот факт, что в современных компьютерах битовый сдвиг и побитовое ИЛИ являются атомарными операциями. По сути, это примитивный алгоритм поиска с небольшой оптимизацией, благодаря которой за одну операцию производится до 32 сравнений одновременно (или до 64, в зависимости от разрядности машины). Легко переделывается на приблизительный поиск. Вычислительная сложность — O(|needle|·|haystack|) операций с крайне малой константой. На предварительную обработку идёт O(|needle|·|Σ|) операций и памяти, где Σ — алфавит. Если же длина шаблона поиска (в символах) не превышает длину машинного слова (в битах), сложность получается O(|haystack|) и O(|needle|+|Σ|) соответственно. Предполагается, что алгоритм разработал в 1964 году венгр Балинт Дёмёльки. Но популярность он приобрёл в 1990-е годы благодаря работам чилийца Рикардо Баэса-Ятеса и уругвайца Гастона Гоннета. На двоичном алгоритме основана известная утилита приблизительного поиска <a href="/w/index.php?title=Agrep&action=edit&redlink=1" class="new" title="Agrep (страница отсутствует)">agrep</a>. (ru)
- Bitap算法（或称为shift-or、shift-and、Baeza-Yates–Gonnet算法）是一种字符串近似匹配算法。该算法可判断给定的文本是否包含与定义模式“近似相等”的子字符串。其中，根据萊文斯坦距離 – 如果子字符串和定义模式彼此在给定距离“K”之内，则该算法认为他们近似。该算法预先计算一组位掩码，其中每个位掩码的每一个元素都包含一个模式。然后，它可以通过按位操作以完成大部分工作。 可以将Bitap算法作为Unix软件开发工具agrep的基础算法之一，它由、和开发。Udi Manber和Sun Wu的原始论文对算法进行了扩展，以处理一般正则表达式的模糊匹配。 由于算法需要的数据结构，它在小于固定长度（通常是字长）的模式上表现最佳。但是，一旦针对给定的字长“m”进行定义，则其运行时间是完全可以预测的——无论文本的结构或模式如何，它的运行时间均为O（"mn"）。 搜索精确字符串的Bitap算法在1964年由BálintDömölki发明，并由R. K. Shyamasundar在1977年进行了扩充。随后，在1989年由和开发，该算法也延伸到了处理字符、通配符和不匹配字符。1991年，和Sun Wu对其进行了扩展，以处理插入和删除操作（完全的模糊字符串搜索）。此算法后来在1996年由 Baeza-Yates和改进。 (zh)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 9635 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- L'algorithme de Baeza-Yates-Gonnet plus connu sous le nom de Shift-Or ou encore Bitap est un algorithme de recherche de sous-chaîne.Sa version en recherche exacte a été publiée par en 1964 avant d'être adaptée en 1996 par et pour satisfaire une recherche approximative. L'algorithme utilise des opérations bit à bit ce qui lui permet d'atteindre une bonne performance. Cependant une limitation inhérente est que la sous-chaîne ne peut dépasser la taille d'un mot machine. Une autre force de Shift-Or est sa capacité à être facilement adapté pour faire des recherches approximatives. (fr)
- Bitapアルゴリズム（英: Bitap algorithm）とは、ビット演算の並列性を利用した文字列探索アルゴリズムである。Baeza–Yates–Gonnetアルゴリズムや、shift-andアルゴリズム・shift-orアルゴリズムとも呼ばれる（andとorがあるのは、ブール代数の双対性にもとづくバリエーションである）。レーベンシュタイン距離などの編集距離に基づく「似た」文字列を見つけ出すに利用できることが、他の文字列探索アルゴリズムにない特徴である。 (ja)
- Bitap算法（或称为shift-or、shift-and、Baeza-Yates–Gonnet算法）是一种字符串近似匹配算法。该算法可判断给定的文本是否包含与定义模式“近似相等”的子字符串。其中，根据萊文斯坦距離 – 如果子字符串和定义模式彼此在给定距离“K”之内，则该算法认为他们近似。该算法预先计算一组位掩码，其中每个位掩码的每一个元素都包含一个模式。然后，它可以通过按位操作以完成大部分工作。 可以将Bitap算法作为Unix软件开发工具agrep的基础算法之一，它由、和开发。Udi Manber和Sun Wu的原始论文对算法进行了扩展，以处理一般正则表达式的模糊匹配。 由于算法需要的数据结构，它在小于固定长度（通常是字长）的模式上表现最佳。但是，一旦针对给定的字长“m”进行定义，则其运行时间是完全可以预测的——无论文本的结构或模式如何，它的运行时间均为O（"mn"）。 搜索精确字符串的Bitap算法在1964年由BálintDömölki发明，并由R. K. Shyamasundar在1977年进行了扩充。随后，在1989年由和开发，该算法也延伸到了处理字符、通配符和不匹配字符。1991年，和Sun Wu对其进行了扩展，以处理插入和删除操作（完全的模糊字符串搜索）。此算法后来在1996年由 Baeza-Yates和改进。 (zh)
- 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. (en)
- Der Baeza-Yates-Gonnet-Algorithmus bzw. Shift-or-Algorithmus, der auch unter den Namen Shift-and oder Bitap bekannt ist, löst das String-Matching-Problem, indem er einen nichtdeterministischen Automaten simuliert. Unter anderem wird eine Abwandlung dieses Algorithmus bei dem Unix-Tool grep benutzt. (de)
- Двоичный алгоритм поиска подстроки (также bitap algorithm, shift-or algorithm) — алгоритм поиска подстроки, использующий тот факт, что в современных компьютерах битовый сдвиг и побитовое ИЛИ являются атомарными операциями. По сути, это примитивный алгоритм поиска с небольшой оптимизацией, благодаря которой за одну операцию производится до 32 сравнений одновременно (или до 64, в зависимости от разрядности машины). Легко переделывается на приблизительный поиск. (ru)
|
| rdfs:label
|
- Baeza-Yates-Gonnet-Algorithmus (de)
- Bitap algorithm (en)
- Algorithme de Baeza-Yates-Gonnet (fr)
- Bitapアルゴリズム (ja)
- Двоичный алгоритм поиска подстроки (ru)
- Bitap算法 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
