Anar al contingut

Algoritmes de busca d'subcadena

De L'Enciclopèdia, la wikipedia en valencià
Archiu:String search.png
Arquitectura de l'algoritme de busca de cadenes

A este tipo d'algoritmes també se'ls crida Algoritmes de patrons en un text, algoritmes de emparejamiento de seqüències, algoritmes de casament de seqüències o simplement pel seu nom en anglés string matching. Este tipo d'algoritmes perseguixen trobar subcadena/s en alguna propietat en una cadena de caràcters.

Terminologia

[editar | editar còdic]

Normalment es denomina patró/és a la/ subcadena/s buscada/s i text a la cadena en la que es realisa la busca. Se solen amprar les lletres m i n per a referir-nos a la llongitut d'un patró i a la llongitut del text respectivament. Podem assumir que n>m

Classificació

[editar | editar còdic]

Este tipo d'algoritmes es poden classificar segons el número de subcadena que s'intenten buscar en simples, es busca només una subcadena, i múltiples, es busquen vàries subcadena.[1][2]

Algoritmes de busca simple de subcadena

[editar | editar còdic]

També anomenats per la seua denominació en anglés Single string Matching. En este tipo d'algoritmes només es busca una subcadena a la que cridem patró, és dir l'objectiu és trobar totes les ocurrències del patró p dins del text. Este tipo d'algoritmes se solen agrupar en algun dels següents tipos[1]

  1. Força bruta. L'idea és anar esgolant el patró sobre el text d'esquerra a dreta, comparant-ho en les subcadena del mateix tamany que escomencen en cada caràcter del text.
  2. Llegir tots els caràcters del text un a un modificant en cada pas algunes variables que permeten identificar possibles ocurrències. A este tipo pertanyen els algoritmes de Knuth-Morris-Pratt,[3] Shift-Or[4] o busca simple en autómata determinista.
  3. Buscar el patró en una finestra que s'esgola a lo llarc del text. Per a cada posició d'esta finestra busquem de dreta a esquerra un sufix de la finestra que corresponga a un sufix del patró. A este tipo pertanyen els algoritmes de Boyer-Moore,[5] Boyer-Moore-Horspool[6] i Sunday Quick Search.[7] Este tipo d'algoritmes no solen funcionar be quan el tamany del patró és chicotet i hi ha una provabilitat alta de trobar-ho en el text.
  1. La busca es realisa de dreta a esquerra dins d'una finestra, pero en este esquema es busca el sufix més llarc en la finestra que és subcadena del patró. Eixemples d'este tipo d'algoritmes són BDM,[8] BNDM[9] i BOM.[10] Este tipo d'algoritmes per a patrons menuts no solen funcionar be.
  2. Esquemes basats en funcions hash. Eixemple d'este tipo d'algoritmes és el de Karp-Rabin.[11]

Algoritmes de busca múltiple de subcadena

[editar | editar còdic]

També anomenats per la seua denominació en anglés Multiple String Matching. Ara no tenim un sol patró p a buscar sino que contem en un conjunt P={p1,..., pl} de patrons. La solució que se sol adoptar és l'extensió dels esquemes anteriors per al cas múltiple. Per tant tenim els següents subtipos:

  1. Força bruta
  2. Extensió del tipo 2 d'algoritmes de busca simple de subcadena. D'este tipo d'algoritmes són els d'Aho-Corasick,[12] Multiple Shift-And i busca múltiple en autómata determinista.
  3. Extensió del tipo 3 d'algoritmes de busca simple de subcadena. D'este tipo són els algoritmes de Commentz-Walter,[13] Set Horspool, Wu-Manber.[14]
  4. Extensió del tipo 4 d'algoritmes de busca simple de subcadena. D'este tipo són els algoritmes SBOM, Multiple BNDM,[15] DAWG-MATCH.[16]
  5. Extensió del tipo 5 d'algoritmes de busca simple de subcadena

Referències

[editar | editar còdic]
  1. ↑ 1,0 1,1 Román Roset Mayals,Disseny d'una aplicació bioinformática per a l'estudi de repeticions de patrons en cadenes de DNA. Memòria 2003
  2. ↑ Sergio Talens-Oliag Anàlisis d'algoritmes de busca d'un sol patró. Proyecte Fi de Carrera 1997. O Politècnica de Valéncia
  3. ↑ D. E. Knuth, J. H. Morris, and V. R. Pratt. Fast pattern matching in strings. SIAM J.Comput, 6(2):323–350, 1977
  4. ↑ R. Baeza-Yates and G. Gonnet. A new approach to text searching. Comm. ACM, 35(10):74–82, 1992
  5. ↑ R. S. Boyer and J. S. Moore. A fast string searching algorithm. Comm. ACM, 20(10):762–772, 1977
  6. ↑ R. Horspool. Practical fast searching in strings. Softw. Pract. Exp.,10(6):501–506, 1980
  7. ↑ Daniel M. Sunday. A Very Fast Substring Search Algorithm. Comunications of the ACM 33 (8),132–142 (Agost de 1990)
  8. ↑ A. Czumaj, M. Crochemore, L. Gasieniec, S. Jarominek, W. Plandowski, T. Lecroq, and W. Rytter. Speeding up two string-matching algorithms. Algorithmica, 12:247–267, 1994.
  9. ↑ G. Navarro and M. Raffinot. A bit-parallel approach to suffix automata:Fast estendre string matching. In Proceedings of the 9th Annual Symposium on Combinatorial Pattern Matching, number 1448 in Lecture Notes in Computer Science, pages 14–33. Springer-Verlag, Berlin, 1998
  10. ↑ Cyril Allauzen, Maxime Crochemore, and Mathieu Raffinot. Factor oracle:A new structure for pattern matching. In Conference on Current Trends in Theory and Practice of Informatics, pages 295–310, 1999.
  11. ↑ Karp, R. M. i Rabin, M. O.. Efficient Randomized Pattern Matching Algorithms. IBM J. Res.Develop.31 (2), 249–260 (1987)
  12. ↑ A. V. Aho and M. Corasick. Efficient string matching: An aid to bibliographic search. Comm. ACM, 18(6):333–340, 1975
  13. ↑ B. Commentz-Walter. A string matching algorithm fast on the average. In 6th, number 71 in Lecture Notes in Computer Science, pages 118–132. H.A.Maurer, 1979
  14. ↑ S. Wu and U. Manber. A fast algorithm for multi-pattern searching. Technical Report TR-94-17, Chung-Cheng University, 1994
  15. ↑ M. Crochemore and W.Rytter. Text Algorithms. Oxford University Press,1994.
  16. ↑ Maxime Crochemore, Artur Czumaj, Leszek Gasieniec, Thierry Lecroq,Wojciech Plandowski, and Wojciech Rytter. Fast practical multi-pattern matching. Information Processing Letters, 71(3-4):107–113, 1999.


Referències

[editar | editar còdic]


Obtingut de «https://www.lenciclopedia.org/w/index.php?title=Algoritmes_de_busca_d%27subcadena&oldid=831510»