Boyer–Moore string-search algorithm (original) (raw)
Der Boyer-Moore-Algorithmus ist ein String-Matching-Algorithmus. Der Algorithmus wird dazu genutzt, um in einem Text T einen bestimmten Teiltext (Muster M) zu finden und wurde 1977 von Robert S. Boyer und J Strother Moore entwickelt.
| Property | Value |
|---|---|
| dbo:abstract | Der Boyer-Moore-Algorithmus ist ein String-Matching-Algorithmus. Der Algorithmus wird dazu genutzt, um in einem Text T einen bestimmten Teiltext (Muster M) zu finden und wurde 1977 von Robert S. Boyer und J Strother Moore entwickelt. (de) In computer science, the Boyer–Moore string-search algorithm is an efficient string-searching algorithm that is the standard benchmark for practical string-search literature. It was developed by Robert S. Boyer and J Strother Moore in 1977. The original paper contained static tables for computing the pattern shifts without an explanation of how to produce them. The algorithm for producing the tables was published in a follow-on paper; this paper contained errors which were later corrected by Wojciech Rytter in 1980. The algorithm preprocesses the string being searched for (the pattern), but not the string being searched in (the text). It is thus well-suited for applications in which the pattern is much shorter than the text or where it persists across multiple searches. The Boyer–Moore algorithm uses information gathered during the preprocess step to skip sections of the text, resulting in a lower constant factor than many other string search algorithms. In general, the algorithm runs faster as the pattern length increases. The key features of the algorithm are to match on the tail of the pattern rather than the head, and to skip along the text in jumps of multiple characters rather than searching every single character in the text. (en) El algoritmo de búsqueda de cadenas Boyer-Moore es un particularmente eficiente algoritmo de búsqueda de cadenas, y ha sido el punto de referencia estándar para la literatura de búsqueda de cadenas práctica. Fue desarrollado por y en 1977. El algoritmo preprocesa la cadena objetivo (clave) que está siendo buscada, pero no en la cadena en que se busca (no como algunos algoritmos que procesan la cadena en que se busca y pueden entonces amortizar el coste del preprocesamiento mediante búsqueda repetida). El tiempo de ejecución del algoritmo Boyer-Moore, aunque es lineal en el tamaño de la cadena siendo buscada, puede tener un factor significativamente más bajo que muchos otros algoritmos de búsqueda: no necesita comprobar cada carácter de la cadena que es buscada, puesto que salta algunos de ellos. Generalmente el algoritmo es más rápido cuanto más grande es la clave que es buscada, usa la información conseguida desde un intento para descartar tantas posiciones del texto como sean posibles en donde la cadena no coincida. (es) Algoritme Boyer-Moore adalah salah satu algoritme pencarian string, dipublikasikan oleh , dan pada tahun 1977. Algoritme ini dianggap sebagai algoritme yang paling efisien pada aplikasi umum. Tidak seperti algoritme pencarian string yang ditemukan sebelumnya, algoritme Boyer-Moore mulai mencocokkan karakter dari sebelah kanan pattern. Ide di balik algoritme ini adalah bahwa dengan memulai pencocokan karakter dari kanan, dan bukan dari kiri, maka akan lebih banyak informasi yang didapat. (in) L'algorithme de Boyer-Moore est un algorithme de recherche de sous-chaîne particulièrement efficace. Il a été développé par Robert S. Boyer et J Strother Moore en 1977. (fr) In informatica, l'algoritmo di Boyer-Moore è un algoritmo di confronto fra stringhe efficiente che rappresenta il principale punto di riferimento nel suo ambiente. È stato sviluppato da e nel 1977. L'algoritmo preprocessa la stringa da cercare (il pattern), ma non la stringa esaminata (il testo). È quindi particolarmente adatto per applicazioni in cui il pattern è molto più breve del testo o persiste su più ricerche. L'algoritmo di Boyer–Moore utilizza informazioni raccolte durante la fase di preprocessamento per poter saltare sezioni del testo, risultando in un fattore costante più basso rispetto a molti altri algoritmi su stringhe. In generale, l'algoritmo è eseguito più velocemente con l'aumentare della lunghezza del pattern. La caratteristica fondamentale dell'algoritmo è il confronto in coda del pattern piuttosto che in testa, e la possibilità di muoversi lungo il testo saltando interi gruppi di caratteri piuttosto che verificare ogni singolo carattere presente nel testo. (it) ボイヤー-ムーア文字列検索アルゴリズム（Boyer-Moore String Search Algorithm）は、効率的な文字列検索アルゴリズムの一種。Robert S. Boyer と J Strother Moore が 1977年に開発した。ボイヤー-ムーア法とも呼ばれる。 このアルゴリズムでは検索文字列（パターン）の前処理を行い、検索対象テキストの前処理は行わない。したがって、テキストについて何度も検索を行わない場合に適している（他のアルゴリズムではテキスト側に前処理を施し、繰り返し検索を行うことで前処理のコストを償却する）。テキスト上の全文字をチェックする必要はなく、前処理で得た情報を活用してスキップしながら処理していく。一般にパターン文字列が長いほど検索が高速化される。検索文字列とテキストの間での不一致が発生するたびに、不一致であったという情報を最大限に利用して照合しなくてもいい位置を可能な限り排除することで、効率を向上させている。 (ja) Em ciência da computação, o algoritmo de busca de expressões Boyer-Moore (Boyer-Moore string search algorithm) é um eficiente algoritmo de busca que é o padrão de qualidade para busca prática de expressões em literatura. Foi desenvolvido por e em 1977. O algoritmo pré-processa a string sendo procurada (o padrão), mas não a string em que é feito a busca (o texto). É ainda bem aproveitado para aplicações em que o padrão é muito menor do que o texto ou onde persiste por multiplas buscas. O algoritmo BM (Boyer-Moore) usa informação reunida durante o passo de pré-processamento para pular seções do texto, resultando em um constante fator baixo do que muitos outros algoritmos. Em geral, o algoritmo roda mais rápido de acordo com o tamanho do padrão aumenta. As características chaves do algoritmo são combinar na cauda do padrão ao invés da cabeça, e pular pelo texto em deslocamentos de multiplos caracteres ao invés de procurar cada caractere no texto. (pt) Algorytm Boyera i Moore'a – algorytm poszukiwania wzorca w tekście. Polega na porównywaniu, zaczynając od ostatniego elementu wzorca. Zalety: * jeżeli okaże się, że znak, który aktualnie sprawdzamy, nie należy do wzorca możemy przeskoczyć w analizie tekstu o całą długość wzorca * z reguły skoki wzorca są większe od 1 (można porównać z algorytmem Knutha-Morrisa-Pratta) (pl) Алгоритм поиска строки Бойера — Мура — алгоритм общего назначения, предназначенный для поиска подстроки в строке. Разработан Робертом Бойером и Джеем Муром в 1977 году. Преимущество этого алгоритма в том, что ценой некоторого количества предварительных вычислений над шаблоном (но не над строкой, в которой ведётся поиск), шаблон сравнивается с исходным текстом не во всех позициях — часть проверок пропускается как заведомо не дающая результата. Общая оценка вычислительной сложности современного варианта алгоритма Бойера — Мура — , если не используется таблица стоп-символов (смотрите ниже), и , если используется таблица стоп-символов, где — длина строки, в которой выполняется поиск, — длина шаблона поиска, — алфавит, на котором проводится сравнение. (ru) Алгоритм пошуку рядка Боєра — Мура, — ефективний алгоритм пошуку рядка, який є еталоном при практичних дослідженнях алгоритмів пошуку рядка. Був розроблений і у 1977 році. Перевага цього алгоритму в тому, що ціною деякої кількості попередніх обчислень над зразком або шаблоном (але не над рядком, в якому ведеться пошук) шаблон порівнюється з вихідним текстом не у всіх позиціях — частина перевірок пропускаються як такі, що не дадуть результату. Цей алгоритм швидко працює у ситуаціях коли зразок набагато коротший від тексту пошуку, або коли відбувається пошук в декількох документах. Зазвичай, чим довше зразок, тим швидше працює алгоритм. Загальна оцінка обчислювальної складності алгоритму — O(|haystack |
| dbo:wikiPageExternalLink | http://dlang.org/phobos/std_algorithm_searching.html%23boyerMooreFinder http://www.cs.utexas.edu/users/moore/best-ideas/string-searching/fstrpos-example.html http://www.cs.utexas.edu/~moore/publications/fstrpos.pdf https://golang.org/src/strings/search.go http://www.cs.nyu.edu/cs/faculty/cole/papers/CHPZ95.ps https://yurichev.com/news/20210421_boyer_moore/ http://www.boost.org/doc/libs/1_58_0/libs/algorithm/doc/html/algorithm/Searching.html%23the_boost_algorithm_library.Searching.BoyerMoore |
| dbo:wikiPageID | 684709 (xsd:integer) |
| dbo:wikiPageLength | 35779 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1100446170 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Boost_(C++_libraries) dbr:Boyer–Moore–Horspool_algorithm dbr:Algorithm dbr:Apostolico–Giancarlo_algorithm dbr:Vaughan_Pratt dbr:Preprocessor dbr:Go_(programming_language) dbr:Andrew_Odlyzko dbr:Computer_science dbr:Zvi_Galil dbr:Leonidas_J._Guibas dbr:String_(computer_science) dbr:C++ dbc:String_matching_algorithms dbr:GNU dbr:Galil_rule dbr:James_H._Morris dbr:D_(programming_language) dbr:Grep dbc:Articles_with_example_C_code dbc:Articles_with_example_Java_code dbc:Articles_with_example_Python_(programming_language)_code dbr:J_Strother_Moore dbr:Donald_Knuth dbr:Brute-force_search dbr:Raita_algorithm dbr:Robert_S._Boyer dbr:Wojciech_Rytter dbr:Substring dbr:Richard_J._Cole dbr:String-searching_algorithm dbr:]_for_a_in_range(ALPHABET_SIZE)] dbr:-1]_for_a_in_range(ALPHABET_SIZE)] |
| dbp:bestTime | Θ preprocessing + Ω matching (en) |
| dbp:class | dbr:String-searching_algorithm |
| dbp:data | dbr:String_(computer_science) |
| dbp:name | Boyer–Moore string search (en) |
| dbp:side | right (en) |
| dbp:space | Θ (en) |
| dbp:time | Θ preprocessing + O matching (en) |
| dbp:width | 340 (xsd:integer) 380 (xsd:integer) |
| dbp:wikiPageUsesTemplate | dbt:= dbt:Commons_category dbt:For dbt:Math dbt:Mvar dbt:Reflist dbt:Short_description dbt:Tmath dbt:Float_begin dbt:Float_end dbt:Infobox_algorithm dbt:Strings |
| dcterms:subject | dbc:String_matching_algorithms dbc:Articles_with_example_C_code dbc:Articles_with_example_Java_code dbc:Articles_with_example_Python_(programming_language)_code |
| rdfs:comment | Der Boyer-Moore-Algorithmus ist ein String-Matching-Algorithmus. Der Algorithmus wird dazu genutzt, um in einem Text T einen bestimmten Teiltext (Muster M) zu finden und wurde 1977 von Robert S. Boyer und J Strother Moore entwickelt. (de) Algoritme Boyer-Moore adalah salah satu algoritme pencarian string, dipublikasikan oleh , dan pada tahun 1977. Algoritme ini dianggap sebagai algoritme yang paling efisien pada aplikasi umum. Tidak seperti algoritme pencarian string yang ditemukan sebelumnya, algoritme Boyer-Moore mulai mencocokkan karakter dari sebelah kanan pattern. Ide di balik algoritme ini adalah bahwa dengan memulai pencocokan karakter dari kanan, dan bukan dari kiri, maka akan lebih banyak informasi yang didapat. (in) L'algorithme de Boyer-Moore est un algorithme de recherche de sous-chaîne particulièrement efficace. Il a été développé par Robert S. Boyer et J Strother Moore en 1977. (fr) ボイヤー-ムーア文字列検索アルゴリズム（Boyer-Moore String Search Algorithm）は、効率的な文字列検索アルゴリズムの一種。Robert S. Boyer と J Strother Moore が 1977年に開発した。ボイヤー-ムーア法とも呼ばれる。 このアルゴリズムでは検索文字列（パターン）の前処理を行い、検索対象テキストの前処理は行わない。したがって、テキストについて何度も検索を行わない場合に適している（他のアルゴリズムではテキスト側に前処理を施し、繰り返し検索を行うことで前処理のコストを償却する）。テキスト上の全文字をチェックする必要はなく、前処理で得た情報を活用してスキップしながら処理していく。一般にパターン文字列が長いほど検索が高速化される。検索文字列とテキストの間での不一致が発生するたびに、不一致であったという情報を最大限に利用して照合しなくてもいい位置を可能な限り排除することで、効率を向上させている。 (ja) Algorytm Boyera i Moore'a – algorytm poszukiwania wzorca w tekście. Polega na porównywaniu, zaczynając od ostatniego elementu wzorca. Zalety: * jeżeli okaże się, że znak, który aktualnie sprawdzamy, nie należy do wzorca możemy przeskoczyć w analizie tekstu o całą długość wzorca * z reguły skoki wzorca są większe od 1 (można porównać z algorytmem Knutha-Morrisa-Pratta) (pl) 在计算机科学里，博耶-穆尔字符串搜索算法是一种非常高效的字符串搜索算法。它由和设计于1977年。此算法仅对搜索目标（关键字）进行，而非被搜索的字符串。虽然博耶-穆尔算法的执行时间同样线性依赖于被搜索字符串的大小，但是通常仅为其它算法的一小部分：它不需要对被搜索的字符串中的字符进行逐一比较，而会跳过其中某些部分。通常搜索关键字越长，算法速度越快。它的效率来自于这样的事实：对于每一次失败的匹配尝试，算法都能够使用这些信息来排除尽可能多的无法匹配的位置。 (zh) In computer science, the Boyer–Moore string-search algorithm is an efficient string-searching algorithm that is the standard benchmark for practical string-search literature. It was developed by Robert S. Boyer and J Strother Moore in 1977. The original paper contained static tables for computing the pattern shifts without an explanation of how to produce them. The algorithm for producing the tables was published in a follow-on paper; this paper contained errors which were later corrected by Wojciech Rytter in 1980. The algorithm preprocesses the string being searched for (the pattern), but not the string being searched in (the text). It is thus well-suited for applications in which the pattern is much shorter than the text or where it persists across multiple searches. The Boyer–Moore alg (en) El algoritmo de búsqueda de cadenas Boyer-Moore es un particularmente eficiente algoritmo de búsqueda de cadenas, y ha sido el punto de referencia estándar para la literatura de búsqueda de cadenas práctica. Fue desarrollado por y en 1977. El algoritmo preprocesa la cadena objetivo (clave) que está siendo buscada, pero no en la cadena en que se busca (no como algunos algoritmos que procesan la cadena en que se busca y pueden entonces amortizar el coste del preprocesamiento mediante búsqueda repetida). El tiempo de ejecución del algoritmo Boyer-Moore, aunque es lineal en el tamaño de la cadena siendo buscada, puede tener un factor significativamente más bajo que muchos otros algoritmos de búsqueda: no necesita comprobar cada carácter de la cadena que es buscada, puesto que salta algunos (es) In informatica, l'algoritmo di Boyer-Moore è un algoritmo di confronto fra stringhe efficiente che rappresenta il principale punto di riferimento nel suo ambiente. È stato sviluppato da e nel 1977. L'algoritmo preprocessa la stringa da cercare (il pattern), ma non la stringa esaminata (il testo). È quindi particolarmente adatto per applicazioni in cui il pattern è molto più breve del testo o persiste su più ricerche. L'algoritmo di Boyer–Moore utilizza informazioni raccolte durante la fase di preprocessamento per poter saltare sezioni del testo, risultando in un fattore costante più basso rispetto a molti altri algoritmi su stringhe. In generale, l'algoritmo è eseguito più velocemente con l'aumentare della lunghezza del pattern. La caratteristica fondamentale dell'algoritmo è il confront (it) Em ciência da computação, o algoritmo de busca de expressões Boyer-Moore (Boyer-Moore string search algorithm) é um eficiente algoritmo de busca que é o padrão de qualidade para busca prática de expressões em literatura. Foi desenvolvido por e em 1977. O algoritmo pré-processa a string sendo procurada (o padrão), mas não a string em que é feito a busca (o texto). É ainda bem aproveitado para aplicações em que o padrão é muito menor do que o texto ou onde persiste por multiplas buscas. O algoritmo BM (Boyer-Moore) usa informação reunida durante o passo de pré-processamento para pular seções do texto, resultando em um constante fator baixo do que muitos outros algoritmos. Em geral, o algoritmo roda mais rápido de acordo com o tamanho do padrão aumenta. As características chaves do algoritm (pt) Алгоритм пошуку рядка Боєра — Мура, — ефективний алгоритм пошуку рядка, який є еталоном при практичних дослідженнях алгоритмів пошуку рядка. Був розроблений і у 1977 році. Перевага цього алгоритму в тому, що ціною деякої кількості попередніх обчислень над зразком або шаблоном (але не над рядком, в якому ведеться пошук) шаблон порівнюється з вихідним текстом не у всіх позиціях — частина перевірок пропускаються як такі, що не дадуть результату. Цей алгоритм швидко працює у ситуаціях коли зразок набагато коротший від тексту пошуку, або коли відбувається пошук в декількох документах. Зазвичай, чим довше зразок, тим швидше працює алгоритм. (uk) Алгоритм поиска строки Бойера — Мура — алгоритм общего назначения, предназначенный для поиска подстроки в строке. Разработан Робертом Бойером и Джеем Муром в 1977 году. Преимущество этого алгоритма в том, что ценой некоторого количества предварительных вычислений над шаблоном (но не над строкой, в которой ведётся поиск), шаблон сравнивается с исходным текстом не во всех позициях — часть проверок пропускается как заведомо не дающая результата. (ru) |
| rdfs:label | Boyer-Moore-Algorithmus (de) Algoritmo de búsqueda de cadenas Boyer-Moore (es) Boyer–Moore string-search algorithm (en) Algorithme de Boyer-Moore (fr) Algoritma Boyer-Moore (in) Algoritmo di Boyer-Moore (it) ボイヤー-ムーア文字列検索アルゴリズム (ja) Algorytm Boyera i Moore’a (pl) Algoritmo de busca de expressões Boyer-Moore (pt) Алгоритм Бойера — Мура (ru) 博耶-穆尔字符串搜索算法 (zh) Алгоритм Боєра — Мура (uk) |
| owl:sameAs | wikidata:Boyer–Moore string-search algorithm dbpedia-de:Boyer–Moore string-search algorithm dbpedia-es:Boyer–Moore string-search algorithm dbpedia-fa:Boyer–Moore string-search algorithm dbpedia-fr:Boyer–Moore string-search algorithm dbpedia-he:Boyer–Moore string-search algorithm dbpedia-id:Boyer–Moore string-search algorithm dbpedia-it:Boyer–Moore string-search algorithm dbpedia-ja:Boyer–Moore string-search algorithm http://lt.dbpedia.org/resource/Blogo_simbolio_taisyklė dbpedia-pl:Boyer–Moore string-search algorithm dbpedia-pt:Boyer–Moore string-search algorithm dbpedia-ru:Boyer–Moore string-search algorithm dbpedia-sr:Boyer–Moore string-search algorithm dbpedia-th:Boyer–Moore string-search algorithm dbpedia-uk:Boyer–Moore string-search algorithm dbpedia-zh:Boyer–Moore string-search algorithm https://global.dbpedia.org/id/53WmJ |
| prov:wasDerivedFrom | wikipedia-en:Boyer–Moore_string-search_algorithm?oldid=1100446170&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Boyer–Moore_string-search_algorithm |
| is dbo:wikiPageDisambiguates of | dbr:Boyer–Moore |
| is dbo:wikiPageRedirects of | dbr:Boyer-Moore_string_search_algorithm dbr:Boyer_-_Moore_string_search_algorithm dbr:Boyer–Moore_string_search_algorithm dbr:Boyer-Moore_string-search_algorithm dbr:Galil_rule dbr:Turbo_Boyer-Moore_algorithm dbr:Turbo_Boyer–Moore_algorithm dbr:Quick_search dbr:Boyer-Moore_algorithm dbr:Boyer-Moore_string_searching_algorithm dbr:Boyer_Moore_string_search_algorithm dbr:Boyer_moore dbr:Boyer_moore_algorithm dbr:Boyer_moore_string_search_algorithm dbr:Boyer_–_Moore_string_search_algorithm |
| is dbo:wikiPageWikiLink of | dbr:Boyer-Moore_string_search_algorithm dbr:Boyer_-_Moore_string_search_algorithm dbr:Boyer–Moore dbr:Boyer–Moore_string_search_algorithm dbr:List_of_algorithms dbr:Boyer-Moore_string-search_algorithm dbr:Regular_expression dbr:Input_enhancement_(computer_science) dbr:Rabin–Karp_algorithm dbr:Commentz-Walter_algorithm dbr:Two-way_string-matching_algorithm dbr:Galil_rule dbr:Jewels_of_Stringology dbr:J_Strother_Moore dbr:Raita_algorithm dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Richard_J._Cole dbr:String-searching_algorithm dbr:Turbo_Boyer-Moore_algorithm dbr:Turbo_Boyer–Moore_algorithm dbr:Quick_search dbr:Boyer-Moore_algorithm dbr:Boyer-Moore_string_searching_algorithm dbr:Boyer_Moore_string_search_algorithm dbr:Boyer_moore dbr:Boyer_moore_algorithm dbr:Boyer_moore_string_search_algorithm dbr:Boyer_–_Moore_string_search_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Boyer–Moore_string-search_algorithm |