Suchalgorithmen (Boyer-Moore und Co.)

    Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

    Unsere Datenschutzerklärung wurde aktualisiert. Mit der Nutzung unseres Forums akzeptierst Du unsere Datenschutzerklärung. Du bestätigst zudem, dass Du mindestens 16 Jahre alt bist.

    • Suchalgorithmen (Boyer-Moore und Co.)

      ' Suchalgorithmen
      ' - Knuth-Morris-Pratt (KMP)
      ' - Boyer-Moore
      ' - Horspool
      ' - Sunday

      Den Quellcode gibt es hier (weil zu groß):
      [Link zu FileUpload vom Moderator gelöscht]

      und nach dem Tipp von Andreas nun ein 2. Versuch:
      Suchalgorithmen

      P.S.: :wacko:
      Ich war wohl zu schnell. Erstens heißt die Datei "Sortier..." und dann hat dieser Dienstleister gleich einen Virus mitgeliefert...
      Sorry. Ich wußte nicht, das reine Texte als EXE ausgeliefert werden. Dieser Dienstleister ist bei mir unten durch...

      P.P.S.: :roll:
      Klarer Punkt für den Speedy...
      Danke Andreas (schreib ich mir hinter die Löffel)
      Programmieren, das spannendste Detektivspiel der Welt.

      Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von AHT ()

    • Hab mir das Sorgenkind nochmal angeschaut, aber bei mir läuft das einwandfrei durch.

      Brainfuck-Quellcode

      1. ' XProfan 11 (I hope)
      2. ' Suchalgorithmen
      3. ' - Boyer-Moore
      4. ' Diese Algorithmen untersuchen erst den Suchbegriff und bilden eine
      5. ' oder mehrere Sprungtabellen, um den Suchbegriff schneller über den
      6. ' zu untersuchenden Text zu schieben.
      7. ' Wenn diese Prozedur vom eigentlichen Suchen getrennt wird, dann
      8. ' können mit EINER Sprungtabelle mehrere große Textteile nacheinander
      9. ' untersucht werden.
      10. ' Außerdem wird hier mit Adressen gearbeitet, um sowohl in einfachen
      11. ' Strings als auch in Bereichen suchen zu können.
      12. ' Die Routinen sind also geteilt in XXX_Tab und XXX_Search
      13. Proc MinF
      14. Parameters a!,b!
      15. Return if(a! < b!,a!,b!)
      16. EndProc
      17. Proc MaxF
      18. Parameters a!,b!
      19. Return if(a! > b!,a!,b!)
      20. EndProc
      21. Proc MinL
      22. Parameters a&,b&
      23. Return if(a& < b&,a&,b&)
      24. EndProc
      25. Proc MaxL
      26. Parameters a&,b&
      27. Return if(a& > b&,a&,b&)
      28. EndProc
      29. Proc MatchesAt
      30. Parameters SourceStart&, SourceLen&, PatternStart&, PatternLen&, Posi&
      31. Declare j&
      32. j& = 0
      33. While (j& < PatternLen&) and (Char$(PatternStart&,j&,1) = Char$(SourceStart&,Posi& + j&,1))
      34. Inc j&
      35. EndWhile
      36. Return (j& = PatternLen&) 'volle Übereinstimmung
      37. EndProc
      38. ' ==================================
      39. ' - Boyer-Moore
      40. ' untersucht den Suchbegriff und liefert ein dynamisches Array zurück
      41. Proc BoyerMoore_Tab_Bad
      42. Parameters PatternStart&, PatternLen&
      43. Declare Bad_Tab&[]
      44. ' die 'bad rule' des Boyer-Moore
      45. Bad_Tab&[PatternLen&] = 0
      46. WhileLoop 0,255
      47. Bad_Tab&[&loop] = -1
      48. EndWhile
      49. WhileLoop 0,PatternLen& - 1
      50. 'Bad_Tab&[&loop] = 0
      51. Bad_Tab&[Ord(Char$(PatternStart&,&loop,1))] = &loop
      52. EndWhile
      53. Return Bad_Tab&[]
      54. EndProc
      55. ' - Boyer-Moore
      56. ' untersucht den Suchbegriff und liefert ein dynamisches Array zurück
      57. Proc BoyerMoore_Tab_Good
      58. Parameters PatternStart&, PatternLen&
      59. Declare Good_Tab&[], tmp&[], i&,j&
      60. ' die 'good rule' des Boyer-Moore
      61. ' stufe 1
      62. i& = PatternLen& - 1
      63. j& = PatternLen&
      64. tmp&[i&] = j&
      65. WhileLoop 0,PatternLen&
      66. Good_Tab&[&loop] = 0
      67. EndWhile
      68. While i& > 0
      69. While (j& < PatternLen&) and (Char$(PatternStart&,i& - 1,1) <> Char$(PatternStart&,j& - 1,1))
      70. Case Good_Tab&[j&] = 0 : Good_Tab&[j&] = j& - i&
      71. j& = tmp&[j&]
      72. EndWhile
      73. Dec i&
      74. Dec j&
      75. tmp&[i&] = j&
      76. EndWhile
      77. ' stufe 2
      78. j& = tmp&[0]
      79. WhileLoop 0,PatternLen& - 1
      80. Case Good_Tab&[&loop] = 0 : Good_Tab&[&loop] = j&
      81. Case &loop = j& : j& = tmp&[j&]
      82. EndWhile
      83. Return Good_Tab&[]
      84. EndProc
      85. ' ----------------------------------
      86. ' - Boyer-Moore-Algorithmus
      87. Proc BoyerMoore_Search
      88. Parameters SourceStart&, SourceLen&, PatternStart&, PatternLen&, MaxTreffer&, BadTab&[], GoodTab&[]
      89. Declare TrefferTab&[],Treffer&, i&,j&
      90. Treffer& = 0
      91. Case PatternLen& > SourceLen& : Return TrefferTab&[]
      92. i& = 0
      93. While i& <= (SourceLen& - PatternLen&)
      94. j& = PatternLen& - 1
      95. While (j& >= 0) and (Char$(PatternStart&,j&,1) = Char$(SourceStart&,i& + j&,1))
      96. Dec j&
      97. EndWhile
      98. If j& < 0
      99. TrefferTab&[Treffer&] = i&
      100. Inc Treffer&
      101. Inc i&, GoodTab&[0]
      102. Else
      103. Inc i&, MaxL( GoodTab&[j& + 1], j& - BadTab&[Ord(Char$(SourceStart&,i& + j&,1))] )
      104. EndIf
      105. Case (MaxTreffer& <> 0) and (Treffer& >= MaxTreffer&) : BREAK
      106. EndWhile
      107. Return TrefferTab&[]
      108. EndProc
      109. ' ==================================
      110. ' ----------------------------------
      111. ' Testbereich
      112. ' ----------------------------------
      113. Declare Ergebnisse&[],Tab1&[],Tab2&[], lauf&, Quelle$, Muster$
      114. Cls
      115. ' -------------------------------
      116. ' - Boyer-Moore
      117. Clear Ergebnisse&[],Tab1&[],Tab2&[]
      118. Quelle$ = "abababcbababcababcabababcabab"
      119. Muster$ = "ababcabab"
      120. Tab1&[] = BoyerMoore_Tab_Bad(addr(Muster$),len(Muster$))
      121. Tab2&[] = BoyerMoore_Tab_Good(addr(Muster$),len(Muster$))
      122. Ergebnisse&[] = BoyerMoore_Search(addr(Quelle$),len(Quelle$),addr(Muster$),len(Muster$), 5, Tab1&[],Tab2&[] )
      123. Print "\nBoyer-Moore: ";
      124. WhileLoop 0,SizeOf(Ergebnisse&[])-1
      125. Print Ergebnisse&[&loop];";";
      126. EndWhile
      127. Print " "
      128. print Tab(3);"01234567890123456789012345678"
      129. WhileLoop 0,SizeOf(Ergebnisse&[])-1
      130. Print Tab(3);Quelle$
      131. Print Tab(3+Ergebnisse&[&loop]);Muster$
      132. EndWhile
      133. Clear Ergebnisse&[],Tab1&[],Tab2&[]
      134. Quelle$ = "reinesupersauersupesupersupe"
      135. Muster$ = "supersupe"
      136. ' Wenn nur der zu durchsuchende Text sich ändert und
      137. ' das gleiche Suchmuster verwendet wird, dann braucht
      138. ' die Tabelle nicht erneuert zu werden.
      139. ' ---aber hier ändert sich auch der Suchwert---
      140. Tab1&[] = BoyerMoore_Tab_Bad(addr(Muster$),len(Muster$))
      141. Tab2&[] = BoyerMoore_Tab_Good(addr(Muster$),len(Muster$))
      142. Ergebnisse&[] = BoyerMoore_Search(addr(Quelle$),len(Quelle$),addr(Muster$),len(Muster$), 5, Tab1&[],Tab2&[] )
      143. Print "\nBoyer-Moore: ";
      144. WhileLoop 0,SizeOf(Ergebnisse&[])-1
      145. Print Ergebnisse&[&loop];";";
      146. EndWhile
      147. Print " "
      148. print Tab(3);"0123456789012345678901234567"
      149. WhileLoop 0,SizeOf(Ergebnisse&[])-1
      150. Print Tab(3);Quelle$
      151. Print Tab(3+Ergebnisse&[&loop]);Muster$
      152. EndWhile
      153. Print "\nENDE - Taste drücken"
      154. WaitKey
      155. End
      Alles anzeigen
      Programmieren, das spannendste Detektivspiel der Welt.
    • Nun ja, etwas verbesserungsfähig vielleicht.

      Wenn nichts gefunden wurde, dann wird ein leeres dynamisches Array zurückgegeben.

      Mit der Abfrage "WhileLoop 0,SizeOf(Ergebnisse&[])-1" wird dann ja auch die Schleife nicht ausgeführt.

      Ein paar Tester vielleicht, mit Angabe der PrfVersionsnummer? :hilfe:

      Gruß
      Michael
      Programmieren, das spannendste Detektivspiel der Welt.
    • Leere weisse Fläche in $ProfVer=11.2a, weil aus _Search nicht rausgebreakt wird. Habe da so einen Verdacht:
      EDIT: Hat sich erledigt - dank Heinz!
      [...prüfbar mit Codestück-Ersatz beim 1. Testfall

      Quellcode

      1. Tab1&[] = BoyerMoore_Tab_Bad(addr(Muster$),len(Muster$))
      2. :::print sizeof(tab1&[]):whileloop sizeof(tab1&[]):print tab1&[&loop-1],:endwhile
      3. Tab2&[] = BoyerMoore_Tab_Good(addr(Muster$),len(Muster$))
      4. :::print "\n\n",sizeof(tab2&[]):whileloop sizeof(tab2&[]):print tab2&[&loop-1],:endwhile
      Win7-64HomPremSP1,XProfan11.2a,XPIA,JWasm,xpse,IntelCoreQuad2.5GHz/4GB/je1TB HD intern:esataBay:USB3

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von p. specht ()

    • Oops, dann war's doch nicht die Good-Table...
      Danke Heinz! Die Suche geht weiter, diesmal mit 'TraceOn'.
      EDIT: Gefunden :thumbsup: :!:

      XProfan 11.2a kann im INC i&,... Befehl noch keine Funktionen auflösen, MaxL() funktioniert dort nicht. Geht man den Weg über eine Zwischenvariable, klappt alles. Mit folgender Änderung der Proc BoyerMoore_Search klappt es nun auch in älteren XProfan-Versionen!
      Gruss

      P.S. Nochmal großes DANKE an Michael und alle Mitwirkenden!

      Quellcode

      1. Proc BoyerMoore_Search
      2. Parameters SourceStart&,SourceLen&,PatternStart&,PatternLen&,MaxTreffer&,BadTab&[],GoodTab&[]
      3. Declare TrefferTab&[],i&,j&,Treffer&,v11&
      4. Treffer& = 0
      5. Case PatternLen& > SourceLen& : Return TrefferTab&[]
      6. i& = 0
      7. While i& <= (SourceLen& - PatternLen&)
      8. j& = PatternLen& - 1
      9. While (j&>=0) and (Char$(PatternStart&,j&,1) = Char$(SourceStart&,i&+j&,1))
      10. Dec j&
      11. EndWhile
      12. If j&<0
      13. TrefferTab&[Treffer&] = i&
      14. Inc Treffer&
      15. Inc i&,GoodTab&[0]
      16. Else
      17. v11&=MaxL( GoodTab&[j&+1], j&-BadTab&[Ord(Char$(SourceStart&,i&+j&,1))] )
      18. Inc i&,v11&
      19. EndIf
      20. if (MaxTreffer& <> 0) and (Treffer& >= MaxTreffer&)
      21. BREAK
      22. endif
      23. EndWhile
      24. Return TrefferTab&[]
      25. EndProc
      Alles anzeigen
      Win7-64HomPremSP1,XProfan11.2a,XPIA,JWasm,xpse,IntelCoreQuad2.5GHz/4GB/je1TB HD intern:esataBay:USB3

      Dieser Beitrag wurde bereits 6 mal editiert, zuletzt von p. specht ()