n-wymiarowe dopasowanie wzoru

20

Jakie są znane wyniki znalezienia dokładnej n-wymiarowej podtablicy wewnątrz n-wymiarowej tablicy?

W 1D jest to tylko problem dopasowania łańcucha, KMP robi to w czasie liniowym.

W 2D ten dokument pokazał, że można to zrobić w czasie liniowym z niewielką dodatkową przestrzenią.

Czy ten problem można rozwiązać w najgorszym przypadku liniowym dla dowolnego ustalonego wymiaru?

ds.algorithms reference-request string-matching

— Chao Xu
źródło

13

Możesz rozwiązać problem w ustalonej liczbie wymiarów, przedłużając oryginalne rozwiązanie liniowe Bird z 1977 r. Http://www.sciencedirect.com/science/article/pii/0020019077900175 (niestety wymagana subskrypcja).

Ogólną ideą (w 2D) jest krok 1, aby zbudować automat Aho-Corasicka wierszy wzoru 2D, a następnie wprowadzać kolejno wiersze tekstu 2D. Następnie znajdziesz wszystkie pozycje, które wiersze wzoru pasują do tekstu. Aby zakończyć, wystarczy teraz przeprowadzić wyszukiwanie 1D (etykiet) wierszy wzoru we właściwej kolejności w kolumnie na wyjściu z kroku 1, używając KMP say. Wszystko to zajmuje czas liniowy.

Za pomocą tej samej metody można zredukować problem dokładnego dopasowania wymiaru d do problemu wymiaru d-1. W ten sposób otrzymujesz liniowe rozwiązanie czasowe dla dowolnego stałego wymiaru d.

— Raphael
źródło

9

Możliwe jest rozwiązanie tego w prawie (współczynniku up to polilog) liniowym czasie przy użyciu technik FFT. Możesz zajrzeć na papier: http://www.cs.tau.ac.il/~klim/papers/CEPR08.pdf, gdzie używamy technik FFT do dopasowywania jednowymiarowych wzorów. Jeśli chcesz rozwiązać wielowymiarowe dopasowywanie wzorów, wystarczy użyć wielowymiarowego FFT.

— Klim
źródło

Biorąc pod uwagę, że artykuł pochodzi z 2008 roku, zakładam, że algorytmy liniowego czasu nie są jeszcze znane.

— Chao Xu

Dałem to tylko jako przykład techniki, która może być wykorzystana do rozwiązania twojego problemu. Zaletą tego podejścia jest to, że pozwala to również rozwiązać problem z niedopasowaniami i nie obchodzi. Ale tak jak w przypadku dokładnie jednego wzoru dopasowania istnieje liniowy alg czasowy. może być znany z wielowymiarowości.

— Klim

1

Myślę, że podstawowy wynik w dopasowywaniu wzorców za pomocą symboli wieloznacznych pochodzi od Fischera i Patersona z 1974 r., A następnie ciągle poprawiany i upraszczany aż do cs.bris.ac.uk/Publications/pub_master.jsp?id=2000602 (przepraszam za samo cytowanie). Jednak może to być lekka przesada w związku z problemem, o który poprosił PO, biorąc pod uwagę starszą metodę dokładnego dopasowania, o której wspomniałem poniżej.

— Raphael