2-D otsimine

1. 2-D mustrid
2. Variatsioone

Olgu antud muster P mis koosneb m x m märgist

Eesmärk - leia S-st mis koosneb n x n märgist kõik võimalikud P esinemised

Näide S: P: 0100100100100 1010 1010100010010 0010 0100100010100 1010 0101001010010 0100 0111010010100 0100111010010 1000100100001 0100111000100 .............

Muster leidub positsioonil (i,j) vastavalt P esinemise ülemisele vasakule nurgale.

Näites seega positsioonil (7,4)

Variatsioone

• Täpne
• Ligikaudne
• Vabas vormis muster
• Skaleerimine

  01 0011 11 0011 1111 1111

• Jõumeetod

• Bird (1977) ja Baker (1978):

  1. Leia S-ist kõik P read kasutades AC-automaati märkides lõpukohad n x n tabelisse
  2. Otsi abitabelist KMP-ga

  Bird, R.S. 1977. Two-dimensional pattern matching. Inf. Process. Lett. 6(5):168 170.
  Baker, T.P. 1978. A technique for extending rapid exact-match string matching to arrays of more than one dimension. SIAM J. Comput. 7(4):533 541.
  

• Zhu & Takaoka (1989)

  • Esimene algoritm mis oli alla lineaarse
  • Rabin-Karp ridu pidi
  • BM veerge pidi

  Zhu, R.F., Takaoka, T. 1989. A technique for two-dimensional pattern matching. Comm. ACM. 32(9):1110 1120.
  

• Baeza-Yates ja Regnier (1992)

  • BM sarnane
  • Iga m-s rida Commentz-Walteri meetodil
  • Kui leiti potentsiaalne esinemine, siis otsi täpsemalt

    

• Park ja Galil (1992)

  • Elimineerimismeetod
    • Alguses on kõik P esinemised võimalikud (kandidaadid)
    • Võrdleme S-ga. Sell põhjal saab välistada kohe kandidaate
    • Kandidaatide võrdlus tehakse duellina: vähemalt üks kandidaatidest kaotab (kaob)
    • Alles jäänud kandidaatidele tehakse täpne võrdlus
  • O(m² + n²) sõltumata tähestiku suurusest

• Kärkkäinen ja Ukkonen (1994)

  • Optimaalne alla lineaarse otsimisfaas

• Tarhio (1993)

  • Boyer-Moore-Horspooli üldistus 2-D juhule