From Wikipedia, the free encyclopedia
Blogo simbolio taisyklė (arba Boyer-Moore algoritmas) – teksto paieškos ilgoje eilutėje algoritmas.[1]
Algoritmas ieško palyginti trumpos eilutės kitoje (paprastai daug ilgesnėje) iš anksto nežinomoje eilutėje. Tuo jis skiriasi nuo priesagų medžius naudojančių algoritmų, kuriems ilgąja eilutę reikia žinoti iš anksto – medžiui sukurti.
Klasikinis Boyer-Moore algoritmas remiasi trimis paprastomis taisyklėmis:
Blogo simbolio taisyklės taikymas ieškant žodžio LIULA frazėje LŪGNĖS LAPAI LIULA EŽERE.
Taigi skirtingai nuo naiviojo algoritmo, kuris paieškos rėmelį kiekvieną kartą patraukia tik per vieną simbolį, Boyer-Moore algoritmas paprastai rėmelį patraukia gerokai daugiau ir todėl yra pastebimai greitesnis. Jis gerai tinka ieškant teksto fragmentų žmonių kalboje arba baltymų sekose ir sunkiau pritaikomas DNR sekoms, kur abėcėle apribota keturiais simboliais.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.