The Boyer–Moore string search algorithm is a particularly efficient string searching algorithm, and it has been the standard benchmark for the practical string search literature. It was developed by Bob Boyer and J Strother Moore in 1977.
| Property | Value |
|---|
| dbpedia-owl: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.
- The Boyer–Moore string search algorithm is a particularly efficient string searching algorithm, and it has been the standard benchmark for the practical string search literature. It was developed by Bob Boyer and J Strother Moore in 1977. The algorithm preprocesses the target string (key) that is being searched for, but not the string being searched in (unlike some algorithms that preprocess the string to be searched and can then amortize the expense of the preprocessing by searching repeatedly). The execution time of the Boyer-Moore algorithm, while still linear in the size of the string being searched, can have a significantly lower constant factor than many other search algorithms: it doesn't need to check every character of the string to be searched, but rather skips over some of them. Generally the algorithm gets faster as the key being searched for becomes longer. Its efficiency derives from the fact that with each unsuccessful attempt to find a match between the search string and the text it is searching, it uses the information gained from that attempt to rule out as many positions of the text as possible where the string cannot match.
- 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 Bob Boyer y J Strother Moore 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.
- ボイヤー-ムーア文字列検索アルゴリズム（Boyer-Moore String Search Algorithm）は、効率的な文字列検索アルゴリズムの一種。Robert S. Boyer と J Strother Moore が 1977年に開発した。ボイヤー-ムーア法とも呼ばれる。 このアルゴリズムでは検索対象文字列（キー）の前処理を行い、検索対象テキストの前処理は行わない（他のアルゴリズムではテキストに前処理を施し、繰り返し検索を行うことで前処理のコストを償却する）。ボイヤー-ムーア法の実行時間は半線形時間である。テキスト上の全文字をチェックする必要はなく、スキップしながら処理していく。一般にキー文字列が長いほど検索が高速化される。検索文字列とテキストの間での不一致が発生するたびに、不一致であったという情報を最大限に利用して照合しなくてもいい位置を可能な限り排除することで、効率を向上させている。
- 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 KMP)
- Алгоритм Бойера — Мура поиска строки считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Был разработан Робертом Бойером и Джеем Муром в 1977 году. Преимущество этого алгоритма в том, что ценой некоторого количества предварительных вычислений над шаблоном (но не над строкой, в которой ведётся поиск) шаблон сравнивается с исходным текстом не во всех позициях — часть проверок пропускаются как заведомо не дающие результата. Общая оценка вычислительной сложности алгоритма — O(|haystack|+|needle|+|Σ|) на непериодических шаблонах и O(|haystack|·|needle|+|Σ|) на периодических, где haystack — строка, в которой выполняется поиск, needle — шаблон поиска, Σ — алфавит, на котором проводится сравнение. В 1991 году Коул показал, что на непериодических шаблонах за полный проход по строке алгоритм совершит не более 3·|haystack| сравнений.
- L'algorithme de Boyer-Moore est un algorithme de recherche de sous-chaîne particulièrement efficace. Il a été développé par Bob Boyer et J Strother Moore en 1977.
|
| dbpedia-owl:wikiPageExternalLink
| |
| dcterms:subject
| |
| rdf:type
| |
| 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.
- ボイヤー-ムーア文字列検索アルゴリズム（Boyer-Moore String Search Algorithm）は、効率的な文字列検索アルゴリズムの一種。Robert S. Boyer と J Strother Moore が 1977年に開発した。ボイヤー-ムーア法とも呼ばれる。 このアルゴリズムでは検索対象文字列（キー）の前処理を行い、検索対象テキストの前処理は行わない（他のアルゴリズムではテキストに前処理を施し、繰り返し検索を行うことで前処理のコストを償却する）。ボイヤー-ムーア法の実行時間は半線形時間である。テキスト上の全文字をチェックする必要はなく、スキップしながら処理していく。一般にキー文字列が長いほど検索が高速化される。検索文字列とテキストの間での不一致が発生するたびに、不一致であったという情報を最大限に利用して照合しなくてもいい位置を可能な限り排除することで、効率を向上させている。
- 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 KMP)
- The Boyer–Moore string search algorithm is a particularly efficient string searching algorithm, and it has been the standard benchmark for the practical string search literature. It was developed by Bob Boyer and J Strother Moore in 1977.
- 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 Bob Boyer y J Strother Moore en 1977.
- Алгоритм Бойера — Мура поиска строки считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Был разработан Робертом Бойером и Джеем Муром в 1977 году. Преимущество этого алгоритма в том, что ценой некоторого количества предварительных вычислений над шаблоном (но не над строкой, в которой ведётся поиск) шаблон сравнивается с исходным текстом не во всех позициях — часть проверок пропускаются как заведомо не дающие результата.
- L'algorithme de Boyer-Moore est un algorithme de recherche de sous-chaîne particulièrement efficace. Il a été développé par Bob Boyer et J Strother Moore en 1977.
|
| rdfs:label
|
- Boyer-Moore-Algorithmus
- Boyer–Moore string search algorithm
- Algorithme de Boyer-Moore
- Algoritmo de búsqueda de cadenas Boyer-Moore
- ボイヤー-ムーア文字列検索アルゴリズム
- Algorytm Boyera i Moore'a
- Алгоритм Бойера — Мура
|
| owl:sameAs
| |
| foaf:page
| |
| is dbpedia-owl:wikiPageDisambiguates
of | |
| is dbpedia-owl:wikiPageRedirects
of | |
| is owl:sameAs
of | |
| is foaf:primaryTopic
of | |
