30
nov
07

L’algoritmo di Knuth-Morris-Pratt

Lasciamo per un attimo in sospeso il discorso sulla compressione per trattare un argomento altrettanto interessante: la ricerca in un testo. Detto in modo più formale ci interessa di conoscere se un pattern P occorre in un testo T.

Per fare questo possiamo considerare le stringhe come array di caratteri P[0]P[1]…P[m] e T[0]T[1]…T[n], ovviamente con con n>m. L’algoritmo cosiddetto a forza bruta (brute-force o naive) è molto semplice e consiste nel provare tutte le possibili soluzioni. Si scorre quindi tutto il testo e si prova a fare match del pattern. Tutto ciò ha complessità O(nm) in quanto si risolve banalmente in due cicli annidati.

Tale approccio, sebbene apparentemente inefficiente, risulta ragionevole in caso pattern piccoli (< 10 caratteri). Il problema principale di tale algoritmo è che non sfrutta l’informazione del pattern; se ad esempio ci troviamo ad un mismatch possiamo in alcuni casi ricominciare ad effettuare confronti ripartendo da una posizione P[i] con i > 0. Per farlo creiamo una tabella che ci dice di quanto possiamo avanzare senza perdere occorrenze basandoci sul prefisso più lungo del pattern che sia anche un suo suffisso: il bordo. In pratica quando abbiamo un mismatch abbiamo già confrontato parte del pattern con il testo e questa tecnica ci permette di usare quei confronti senza rifarli di nuovo.

Facciamo un esempio e supponiamo di vole cercare BAUBA in BABAUBA. I prefissi del pattern sono ε, B, BA, BAU, BAUB, i suffissi ε, A, BA, UBA, AUBA (ε indica la stringa vuota, che non ha bordo) e i bordi sono ε e BA. Ad un mismatch al carattere in posizione 3 possiamo quindi continuare a matchare dalla A in P invece che dalla B:

  
__v            mismatch
BABAUBA
BAUBA 
___v
BABAUBA
  BAUBA

Il discorso a dire il vero andrebbe ampliato ma, nello stile pragmatico di questi post, evito di tirare fuori automi e scrivo un po’ di codice.

# Knuth-Morris-Pratt string matching
# David Eppstein, UC Irvine, 1 Mar 2002
#
# Modified on 2007-11-27 by Jonathan Masci @ Casapiddu
# Added the verbose option
# to illustrate the algorithm' steps.

class KMP:
	def KnuthMorrisPratt(self, text, patterne, verbose):
		'''Yields all starting positions of copies of the pattern in the text.
	Calling conventions are similar to string.find, but its arguments can be
	lists or iterators, not just strings, it returns all matches, not just
	the first one, and it does not need the whole text in memory at once.
	Whenever it yields, it will have read the text exactly up to and including
	the match that caused the yield.'''

		# Allow indexing into pattern and protect against change during yield
		pattern = list(patterne)
		
		# Build table of shift amounts
		# In shifts we have the compact representation of the search automata
		shifts = [1] * (len(pattern) + 1)
		shift = 1
		
		for pos in range(len(pattern)):
			while shift <= pos and pattern[pos] != pattern[pos-shift]:
				shift += shifts[pos-shift]
			shifts[pos+1] = shift

		if verbose:
			print shifts

		# Do the actual search
		startPos = 0
		matchLen = 0
		readText = ""
		pos = 0
		for c in text:
			readText += c

			if verbose:
				print " " * pos + "v"
				print text
				print " " * (pos - matchLen) + str(patterne)

			while matchLen == len(pattern) or matchLen >= 0 and pattern[matchLen] != c:
				startPos += shifts[matchLen]
				matchLen -= shifts[matchLen]
				print "mismatch"
				
			matchLen += 1
			pos += 1
			if matchLen == len(pattern):
				yield startPos

# Let's do some search
c = KMP()

#Simple search on string
for occ in c.KnuthMorrisPratt("BABAUBA", "BAUBA", True):
	print "Occurrence found at position: " + str(occ)

print "=================================="
#If you want to find on a file you can do it in this way
f = open("KMP.py", 'r')
for occ in c.KnuthMorrisPratt(f.read(), "KMP", False):
	print "Occurrence found at position: " + str(occ)

La complessità di tale algoritmo è O(m+n) e non dipende dalla dimensione dell’alfabeto.

Per eventuali approfondimenti rimando alla sempre autorevolissima wikipedia.

Enjoy!

About these ads

1 Response to “L’algoritmo di Knuth-Morris-Pratt”


  1. 1 claa
    4 febbraio 2010 alle 20:04:36

    azz..che spiegazione…ora ho proprio capitooo!!!!


Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...


Difendi Rebeldia!

Aggiungi ai tuoi feed

 RSS Feed
Add to Google
Add to My Yahoo!
Add to Technorati Favorites!
Add to netvibes

Blog Stats

  • 239,709 hits

Pidduisti on-line

hit counters


Made on a Mac
Last.fm
Giveaway of the Day
highlightInterests("ProfileMusica");
Musicatable.lfmWidget8f0839bdbf919d97305135788e54986d td {margin:0 !important;padding:0 !important;border:0 !important;}table.lfmWidget8f0839bdbf919d97305135788e54986d tr.lfmHead a:hover {background:url(http://cdn.last.fm/widgets/images/en/header/chart/weeklytracks_regular_blue.png) no-repeat 0 0 !important;}table.lfmWidget8f0839bdbf919d97305135788e54986d tr.lfmEmbed object {float:left;}table.lfmWidget8f0839bdbf919d97305135788e54986d tr.lfmFoot td.lfmConfig a:hover {background:url(http://cdn.last.fm/widgets/images/en/footer/blue.png) no-repeat 0px 0 !important;;}table.lfmWidget8f0839bdbf919d97305135788e54986d tr.lfmFoot td.lfmView a:hover {background:url(http://cdn.last.fm/widgets/images/en/footer/blue.png) no-repeat -85px 0 !important;}table.lfmWidget8f0839bdbf919d97305135788e54986d tr.lfmFoot td.lfmPopup a:hover {background:url(http://cdn.last.fm/widgets/images/en/footer/blue.png) no-repeat -159px 0 !important;}

pages

novembre: 2007
L M M G V S D
« ott   dic »
 1234
567891011
12131415161718
19202122232425
2627282930  

Iscriviti

Ricevi al tuo indirizzo email tutti i nuovi post del sito.

%d blogger cliccano Mi Piace per questo: