String match

[tossam]

Buonasera,

Devo fare un progetto di compressione dati, che lavora al livello di bit. Il mio algoritmo per la compressione di dati si basa sulla ricerca di stringhe uguali in una stringa data ( string match). Ovviamente vorrei che il mio algoritmo fosse efficiente. Così ho cercato nel web gli algoritmi di string match... ho trovato molti algoritmi, ma tutti sembrerebbero essere ottimizzati per alfabeti grandi, e ovviamente il mio alfabeto è il più piccolo: {0,1}.
Mi chiedevo se qualcuno fosse a conoscenza di un algoritmo di string matching ottimizzato per alfabeti ridotti.

Grazie

[LeleFT]

Come sempre: linguaggio?


Ciao.

[tossam]

mi serve l'algoritmo... io sviluppo in C# comunque... ma ho postato qua, perchè mi va anche bene uno pseudocodice o un linguaggio diverso da C#, poi se sono in grado traduco...

[tossam]

Per ora sono riuscito a scrivere questo algoritmo. Ma credo che sia "forza bruta" no?
Se mi sapete trovare qualcosa di più efficiente ve ne sarei grato XD.

public int match(bool[]tofnd,int start, int end){
            int j=0; //j è il puntatore della sottosequenza
            int i=start; //i è il puntatore della sequenza
            int posizione = 0; //posizione del match
            bool continua = true; //per continuare il ciclo
            bool trovato = false; //flag che indica se ho rilavato la sottosequenza
            while (continua)
            {
                if (bit[i] == tofnd[j])
                {
                    if (j == 0) posizione = i;
                    if (j < tofnd.Length - 1)
                    {
                        j++;
                    }
                    else
                    {
                        continua = false;
                        trovato = true;
                    }
                    i++;
                }
                else
                {
                    if (j != 0) { i -= j; j = 0; }
                    if (i == end - tofnd.Length) continua = false;
                    i++;
                }
            }
            if (trovato) return posizione;
            return -1;
        } 

bit[] è definito in istanza.
sono di tipo bool[] i vettori in questione poichè come già detto lavoro con i bit.

[Vincenzo1968]

Qui trovi i migliori algoritmi di string matching:

http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf

http://www-igm.univ-mlv.fr/~lecroq/string/node1.html

Vanno bene e per le stringhe normali, e per le stringhe di bit.
Ti consiglio, in particolare, l'algoritmo di Knuth-Morris-Pratt .

[tossam]

grazie mille!!! XD
Mi sarà utile, anche se adesso non so se riesco a fare una traduzione... non capisco il significato di * messo prima del nome di una variabile...
e poi, volevo chiederti se mi puoi spiegare ( se non è troppo complesso), cosa fanno le procedure preKmp e Kmp... il codice non è commentato...
ma se non hai tempo, cercherò di tradurmi il testo in italiano così ci capisco forse qualcosa XD

[oregon]

Originariamente inviato da tossam
non capisco il significato di * messo prima del nome di una variabile...

E' un puntatore C ...

[tossam]

ah... forse mi ricorda qualcosa... ci dovrebbe essere anche in C#, ma probabilmente ha un'altra notazione.

char *x allora, nell'algoritmo di knuth-morris-pratt, è il puntatore ad un vettore di caratteri giusto? poi con x[i] scorro il vettore... nel nostro caso quindi dovrebbe essere la stringa nella quale cerchiamo la ricorrenza....

[Vincenzo1968]

Esempio C:

#include <stdio.h>
#include <string.h>
#include <malloc.h>

void preKmp(char *x, int m, int kmpNext[])
{
	int i, j;

	i = 0;
	j = kmpNext[0] = -1;
	while (i < m)
	{
		while (j > -1 && x[i] != x[j])
			j = kmpNext[j];
		i++;
		j++;
		if (x[i] == x[j])
			kmpNext[i] = kmpNext[j];
		else
			kmpNext[i] = j;
	}
}

int KMP(char *x, char *y)
{
	int m,n;
	int i, j;
	int *kmpNext;

	m = strlen(x);
	n = strlen(y);

	kmpNext = (int*)malloc(sizeof(int)*m);
	if ( !kmpNext )
	{
		printf("Memoria insufficiente.\n");
		return - 1;
	}

	/* Preprocessing */
	preKmp(x, m, kmpNext);

	/* Searching */
	i = j = 0;
	while (j < n)
	{
		while (i > -1 && x[i] != y[j])
			i = kmpNext[i];
		i++;
		j++;
		if (i >= m)
		{
			//OUTPUT(j - i);
			free(kmpNext);
			return j - i;
			//i = kmpNext[i];
		}
	}

	free(kmpNext);
	return -1;;
}

int main()
{
	int res;
	char *x = "stringa";
	//char *x = "ciao";
	char *y = "questa e' la stringa di prova";

	res = KMP(x, y);

	if ( res >= 0 )
		printf("stringa '%s' trovata in posizione %d\n", x, res);
	else
		printf("\nStringa '%s' non trovata.\n", x);

	return 0;
}

Esempio C#:

using System;

namespace KnuthMorrisPratt
{
    class Program
    {
        static void Main(string[] args)
        {
            string x = "stringa";
            //string x = "ciao";
            string y = "questa e' la stringa di prova";

            int res = KMP(x, y);

            if (res >= 0)
                Console.WriteLine("stringa '{0}' trovata in posizione {1}", x, res);
            else
                Console.WriteLine("Stringa '{0}' non trovata.", x);
        }

        static void preKmp(string x, int m, int[] kmpNext)
        {
	        int i = 0;
            int j = kmpNext[0] = -1;

	        while (i < m - 1)
	        {
		        while (j > -1 && x[i] != x[j])
			        j = kmpNext[j];
		        i++;
		        j++;
		        if (x[i] == x[j])
			        kmpNext[i] = kmpNext[j];
		        else
			        kmpNext[i] = j;
	        }
        }

        static int KMP(string x, string y)
        {
	        int m,n;
	        int i, j;

	        m = x.Length;
	        n = y.Length;

            int[] kmpNext = new int[m];

	        /* Preprocessing */
	        preKmp(x, m, kmpNext);

	        /* Searching */
	        i = j = 0;
	        while (j < n)
	        {
		        while (i > -1 && x[i] != y[j])
			        i = kmpNext[i];
		        i++;
		        j++;
		        if (i >= m)
		        {
			        //OUTPUT(j - i);
			        return j - i;
			        //i = kmpNext[i];
		        }
	        }

	        return -1;
        }
    }
}