Document (#31990)

Author
Fichtner, K.
Title
Boyer-Moore Suchalgorithmus
Imprint
Münster : Institut für Wirtschaftsinformatik der Westfälische Wilhelms-Universität Münster
Year
2005
Pages
26 S
Abstract
Die Masse der Suchalgorithmen lässt sich in zwei grundlegend verschiedene Teilbereiche untergliedern. Auf der einen Seite stehen Algorithmen, die auf komplexen Datenstrukturen (häufig baumartig) ganze Datensätze unter Verwendung eines Indizes finden. Als geläufiger Vertreter sei hier die binäre Suche auf sortierten Arrays oder in binären Bäumen genannt. Die andere Gruppe, der sich diese Ausarbeitung widmet, dient dazu, Entsprechungen von Mustern in gegebenen Zeichenketten zu finden. Auf den folgenden Seiten werden nun zunächst einige Begriffe eingeführt, die für das weitere Verständnis und einen Vergleich verschiedener Suchalgorithmen nötig sind. Weiterhin wird ein naiver Suchalgorithmus dargestellt und mit der Idee von Boyer und Moore verglichen. Hierzu wird ihr Algorithmus zunächst informal beschrieben, dann mit Blick auf eine Implementation näher erläutert und anschließend einer Effizienzanalyse - sowohl empirisch als auch theoretisch - unterzogen. Abschließend findet eine kurze Bewertung mit Bezug auf Schwachstellen, Vorzüge und Verbesserungsmöglichkeiten statt, im Zuge derer einige prominente Modifikationen des Boyer-Moore Algorithmus vorgestellt werden.
Content
Ausarbeitung im Rahmen des Seminars Suchmaschinen und Suchalgorithmen, Institut für Wirtschaftsinformatik Praktische Informatik in der Wirtschaft, Westfälische Wilhelms-Universität Münster. - Vgl.: http://www-wi.uni-muenster.de/pi/lehre/ss05/seminarSuchen/Ausarbeitungen/KristoferFichtner.pdf
Theme
Retrievalalgorithmen
Object
Boyer-Moore Suchalgorithmus

Similar documents (content)

  1. Ackermann, J.: Knuth-Morris-Pratt (2005) 0.38 
    0.38445202 = sum of:
  0.38445202 = product of:
    1.2014126 = sum of:
      0.02030173 = weight(abstract_txt:einen in 990) [ClassicSimilarity], result of:
        0.02030173 = score(doc=990,freq=2.0), product of:
          0.061575238 = queryWeight, product of:
            1.0429426 = boost
            4.263084 = idf(docFreq=1699, maxDocs=44421)
            0.013849107 = queryNorm
          0.32970607 = fieldWeight in 990, product of:
            1.4142135 = tf(freq=2.0), with freq of:
              2.0 = termFreq=2.0
            4.263084 = idf(docFreq=1699, maxDocs=44421)
            0.0546875 = fieldNorm(doc=990)
      0.068952106 = weight(abstract_txt:mustern in 990) [ClassicSimilarity], result of:
        0.068952106 = score(doc=990,freq=1.0), product of:
          0.13912839 = queryWeight, product of:
            1.1085372 = boost
            9.06241 = idf(docFreq=13, maxDocs=44421)
            0.013849107 = queryNorm
          0.49560058 = fieldWeight in 990, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            9.06241 = idf(docFreq=13, maxDocs=44421)
            0.0546875 = fieldNorm(doc=990)
      0.12750112 = weight(abstract_txt:zeichenketten in 990) [ClassicSimilarity], result of:
        0.12750112 = score(doc=990,freq=2.0), product of:
          0.16636044 = queryWeight, product of:
            1.2121809 = boost
            9.909708 = idf(docFreq=5, maxDocs=44421)
            0.013849107 = queryNorm
          0.7664149 = fieldWeight in 990, product of:
            1.4142135 = tf(freq=2.0), with freq of:
              2.0 = termFreq=2.0
            9.909708 = idf(docFreq=5, maxDocs=44421)
            0.0546875 = fieldNorm(doc=990)
      0.04695299 = weight(abstract_txt:finden in 990) [ClassicSimilarity], result of:
        0.04695299 = score(doc=990,freq=2.0), product of:
          0.10768607 = queryWeight, product of:
            1.3792315 = boost
            5.6376824 = idf(docFreq=429, maxDocs=44421)
            0.013849107 = queryNorm
          0.43601727 = fieldWeight in 990, product of:
            1.4142135 = tf(freq=2.0), with freq of:
              2.0 = termFreq=2.0
            5.6376824 = idf(docFreq=429, maxDocs=44421)
            0.0546875 = fieldNorm(doc=990)
      0.2545799 = weight(abstract_txt:algorithmus in 990) [ClassicSimilarity], result of:
        0.2545799 = score(doc=990,freq=7.0), product of:
          0.21889918 = queryWeight, product of:
            1.9664344 = boost
            8.037906 = idf(docFreq=38, maxDocs=44421)
            0.013849107 = queryNorm
          1.1630007 = fieldWeight in 990, product of:
            2.6457512 = tf(freq=7.0), with freq of:
              7.0 = termFreq=7.0
            8.037906 = idf(docFreq=38, maxDocs=44421)
            0.0546875 = fieldNorm(doc=990)
      0.1650616 = weight(abstract_txt:suchalgorithmen in 990) [ClassicSimilarity], result of:
        0.1650616 = score(doc=990,freq=1.0), product of:
          0.3136833 = queryWeight, product of:
            2.3539817 = boost
            9.622026 = idf(docFreq=7, maxDocs=44421)
            0.013849107 = queryNorm
          0.5262046 = fieldWeight in 990, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            9.622026 = idf(docFreq=7, maxDocs=44421)
            0.0546875 = fieldNorm(doc=990)
      0.24759239 = weight(abstract_txt:moore in 990) [ClassicSimilarity], result of:
        0.24759239 = score(doc=990,freq=1.0), product of:
          0.47052497 = queryWeight, product of:
            3.5309727 = boost
            9.622026 = idf(docFreq=7, maxDocs=44421)
            0.013849107 = queryNorm
          0.5262046 = fieldWeight in 990, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            9.622026 = idf(docFreq=7, maxDocs=44421)
            0.0546875 = fieldNorm(doc=990)
      0.2704707 = weight(abstract_txt:boyer in 990) [ClassicSimilarity], result of:
        0.2704707 = score(doc=990,freq=1.0), product of:
          0.49908128 = queryWeight, product of:
            3.6365426 = boost
            9.909708 = idf(docFreq=5, maxDocs=44421)
            0.013849107 = queryNorm
          0.5419372 = fieldWeight in 990, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            9.909708 = idf(docFreq=5, maxDocs=44421)
            0.0546875 = fieldNorm(doc=990)
    0.32 = coord(8/25)
  2. Uratani, N.; Takeda, M.: ¬A fast string-searching algorithm for multiple patterns (1993) 0.07 
    0.07104865 = sum of:
  0.07104865 = product of:
    0.88810813 = sum of:
      0.42444408 = weight(abstract_txt:moore in 6274) [ClassicSimilarity], result of:
        0.42444408 = score(doc=6274,freq=1.0), product of:
          0.47052497 = queryWeight, product of:
            3.5309727 = boost
            9.622026 = idf(docFreq=7, maxDocs=44421)
            0.013849107 = queryNorm
          0.902065 = fieldWeight in 6274, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            9.622026 = idf(docFreq=7, maxDocs=44421)
            0.09375 = fieldNorm(doc=6274)
      0.46366405 = weight(abstract_txt:boyer in 6274) [ClassicSimilarity], result of:
        0.46366405 = score(doc=6274,freq=1.0), product of:
          0.49908128 = queryWeight, product of:
            3.6365426 = boost
            9.909708 = idf(docFreq=5, maxDocs=44421)
            0.013849107 = queryNorm
          0.9290351 = fieldWeight in 6274, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            9.909708 = idf(docFreq=5, maxDocs=44421)
            0.09375 = fieldNorm(doc=6274)
    0.08 = coord(2/25)
  3. Korves, J.: Seiten bewerten : Googles PageRank (2005) 0.05 
    0.05350484 = sum of:
  0.05350484 = product of:
    0.33440524 = sum of:
      0.056527574 = weight(abstract_txt:ausarbeitung in 991) [ClassicSimilarity], result of:
        0.056527574 = score(doc=991,freq=1.0), product of:
          0.13505857 = queryWeight, product of:
            1.0922033 = boost
            8.928879 = idf(docFreq=15, maxDocs=44421)
            0.013849107 = queryNorm
          0.4185412 = fieldWeight in 991, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            8.928879 = idf(docFreq=15, maxDocs=44421)
            0.046875 = fieldNorm(doc=991)
      0.030838003 = weight(abstract_txt:einige in 991) [ClassicSimilarity], result of:
        0.030838003 = score(doc=991,freq=1.0), product of:
          0.11360987 = queryWeight, product of:
            1.4166594 = boost
            5.790671 = idf(docFreq=368, maxDocs=44421)
            0.013849107 = queryNorm
          0.2714377 = fieldWeight in 991, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            5.790671 = idf(docFreq=368, maxDocs=44421)
            0.046875 = fieldNorm(doc=991)
      0.045015212 = weight(abstract_txt:zunächst in 991) [ClassicSimilarity], result of:
        0.045015212 = score(doc=991,freq=2.0), product of:
          0.11603477 = queryWeight, product of:
            1.4316982 = boost
            5.852143 = idf(docFreq=346, maxDocs=44421)
            0.013849107 = queryNorm
          0.3879459 = fieldWeight in 991, product of:
            1.4142135 = tf(freq=2.0), with freq of:
              2.0 = termFreq=2.0
            5.852143 = idf(docFreq=346, maxDocs=44421)
            0.046875 = fieldNorm(doc=991)
      0.20202447 = weight(abstract_txt:algorithmus in 991) [ClassicSimilarity], result of:
        0.20202447 = score(doc=991,freq=6.0), product of:
          0.21889918 = queryWeight, product of:
            1.9664344 = boost
            8.037906 = idf(docFreq=38, maxDocs=44421)
            0.013849107 = queryNorm
          0.92291105 = fieldWeight in 991, product of:
            2.4494898 = tf(freq=6.0), with freq of:
              6.0 = termFreq=6.0
            8.037906 = idf(docFreq=38, maxDocs=44421)
            0.046875 = fieldNorm(doc=991)
    0.16 = coord(4/25)
  4. Westermeyer, D.: Adaptive Techniken zur Informationsgewinnung : der Webcrawler InfoSpiders (2005) 0.04 
    0.036481526 = sum of:
  0.036481526 = product of:
    0.30401272 = sum of:
      0.07110148 = weight(abstract_txt:unterzogen in 5333) [ClassicSimilarity], result of:
        0.07110148 = score(doc=5333,freq=1.0), product of:
          0.12990978 = queryWeight, product of:
            1.0711821 = boost
            8.757029 = idf(docFreq=18, maxDocs=44421)
            0.013849107 = queryNorm
          0.5473143 = fieldWeight in 5333, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            8.757029 = idf(docFreq=18, maxDocs=44421)
            0.0625 = fieldNorm(doc=5333)
      0.042440753 = weight(abstract_txt:zunächst in 5333) [ClassicSimilarity], result of:
        0.042440753 = score(doc=5333,freq=1.0), product of:
          0.11603477 = queryWeight, product of:
            1.4316982 = boost
            5.852143 = idf(docFreq=346, maxDocs=44421)
            0.013849107 = queryNorm
          0.36575893 = fieldWeight in 5333, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            5.852143 = idf(docFreq=346, maxDocs=44421)
            0.0625 = fieldNorm(doc=5333)
      0.19047047 = weight(abstract_txt:algorithmus in 5333) [ClassicSimilarity], result of:
        0.19047047 = score(doc=5333,freq=3.0), product of:
          0.21889918 = queryWeight, product of:
            1.9664344 = boost
            8.037906 = idf(docFreq=38, maxDocs=44421)
            0.013849107 = queryNorm
          0.8701288 = fieldWeight in 5333, product of:
            1.7320508 = tf(freq=3.0), with freq of:
              3.0 = termFreq=3.0
            8.037906 = idf(docFreq=38, maxDocs=44421)
            0.0625 = fieldNorm(doc=5333)
    0.12 = coord(3/25)
  5. Fischer, W.L.: Äquivalenz- und Toleranzstrukturen in der Linguistik : zur Theorie der Synonyma (1973) 0.03 
    0.033431314 = sum of:
  0.033431314 = product of:
    0.16715656 = sum of:
      0.040975954 = weight(abstract_txt:gegebenen in 1066) [ClassicSimilarity], result of:
        0.040975954 = score(doc=1066,freq=1.0), product of:
          0.123070925 = queryWeight, product of:
            1.0426058 = boost
            8.523414 = idf(docFreq=23, maxDocs=44421)
            0.013849107 = queryNorm
          0.33294585 = fieldWeight in 1066, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            8.523414 = idf(docFreq=23, maxDocs=44421)
            0.0390625 = fieldNorm(doc=1066)
      0.014501236 = weight(abstract_txt:einen in 1066) [ClassicSimilarity], result of:
        0.014501236 = score(doc=1066,freq=2.0), product of:
          0.061575238 = queryWeight, product of:
            1.0429426 = boost
            4.263084 = idf(docFreq=1699, maxDocs=44421)
            0.013849107 = queryNorm
          0.23550434 = fieldWeight in 1066, product of:
            1.4142135 = tf(freq=2.0), with freq of:
              2.0 = termFreq=2.0
            4.263084 = idf(docFreq=1699, maxDocs=44421)
            0.0390625 = fieldNorm(doc=1066)
      0.061439063 = weight(abstract_txt:entsprechungen in 1066) [ClassicSimilarity], result of:
        0.061439063 = score(doc=1066,freq=1.0), product of:
          0.16122504 = queryWeight, product of:
            1.1933247 = boost
            9.755557 = idf(docFreq=6, maxDocs=44421)
            0.013849107 = queryNorm
          0.38107646 = fieldWeight in 1066, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            9.755557 = idf(docFreq=6, maxDocs=44421)
            0.0390625 = fieldNorm(doc=1066)
      0.023714839 = weight(abstract_txt:finden in 1066) [ClassicSimilarity], result of:
        0.023714839 = score(doc=1066,freq=1.0), product of:
          0.10768607 = queryWeight, product of:
            1.3792315 = boost
            5.6376824 = idf(docFreq=429, maxDocs=44421)
            0.013849107 = queryNorm
          0.22022197 = fieldWeight in 1066, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            5.6376824 = idf(docFreq=429, maxDocs=44421)
            0.0390625 = fieldNorm(doc=1066)
      0.02652547 = weight(abstract_txt:zunächst in 1066) [ClassicSimilarity], result of:
        0.02652547 = score(doc=1066,freq=1.0), product of:
          0.11603477 = queryWeight, product of:
            1.4316982 = boost
            5.852143 = idf(docFreq=346, maxDocs=44421)
            0.013849107 = queryNorm
          0.22859932 = fieldWeight in 1066, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            5.852143 = idf(docFreq=346, maxDocs=44421)
            0.0390625 = fieldNorm(doc=1066)
    0.2 = coord(5/25)