[Alg] Mate van overeenkomst tussen 2 strings *

[xychix]

Ik wil een functie bouwen die van 2 willekeurige strings (plaatsnamen etc.) een matchings percentage kan geven.

nu ben ik al wat aan het coden gegaan in perl, maar ik bedenk steeds meer issues die er ook bij in moeten.

Daarnaast kan ik me niet voorstellen dat er niet een of andere geleerde al een formule / pseudo code heeft uitgedacht.

Deze zou ik dan in perl,C of whatever kunnen bouwen.

Weet iemand de naam van dit algorithme, de betreffende geleerde of iets in die zin ??

alle hints zijn welkom.

doel:
herkennen dat

Amsterdam
amsterdam
Omsterdam
Amstrdam
amsterd.
enzovoorts waarschijnlijk dezelfde betekekenis hebben, hoe waarschijnljik dat dan is wordt aangegeven door de score die uit de functie komt.

[Verwijderd]

http://nl3.php.net/manual/en/function.similar-text.php

dat is de functie die je zoekt denk ik, alleen dan in php. Maar eerst sta ook wat voorbeeldjes en links bij... moet je maar eens kijken

[curry684]

Use the Search Luke: [rml]madwizard in "[ Algoritme (elke taal)] Verschillen tuss..."[/rml]

Als je het daarmee niet kunt weet ik het ook niet meer, incluis code en alles

[SWfreak]

Zoek anders eens in google op edit distance, Hamming distance of Levenstein distance (er moet nog ergens een h in die naam, maar ik weet niet meer waar )

[Apollo_Futurae]

SWfreak schreef op 25 februari 2004 @ 14:23:
Zoek anders eens in google op edit distance, Hamming distance of Levenstein distance (er moet nog ergens een h in die naam, maar ik weet niet meer waar )

Levenshtein .

[SchizoDuckie]

www.php.net/soundex

[Verwijderd]

http://gathering.tweakers.net/forum/view_message/18854214

Volledige code ook nog is

[Tomatoman]

Papa Eend schreef op 25 februari 2004 @ 22:44:
www.php.net/soundex

Het soundex algoritme is in veel situaties inderdaad een uitstekende keuze: supereenvoudig in het gebruik, maar heel waardevol. Het categoriseert op overeenkomsten in uitspraak (is het nou Jansen, Janssen of Janszen?).

[xychix]

C:

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <sys/types.h>

#define DICT      "./dict/dict"
#define MAXWORDS  4096*4
#define MAXDATALEN  1024

char ** readfileinlist(char * filename)
{
    int i;
    char** list;
    char* temp;
    FILE* fp;

    if(!(fp = fopen(filename,"r") ))
    {
        perror("fopen failed");
        exit(1);
    }

    (void *)list = malloc( (MAXWORDS+1) * sizeof(char *) );
    (void *)temp = malloc(MAXDATALEN+1);

    for(i=0; fgets(temp,MAXDATALEN,fp) ;i++)
    {
        char * p;
        if(i>MAXWORDS)
        {
            perror("dictionairy file is to big");
            exit(1);
        }
        p=temp;
        p = p+strlen(temp)-1;
        *p = 0x00;
        list[i] = strdup(temp);
        list[i+1]= NULL;
    }
    return(list);
}

int amatch(const char* string1, const char* string2)
{
    int percent,max,len[2],i,score=0;
    int lang,kort; /* lang stands for long, kort stands for short */
    char* closest;
    char* str[2];
    str[0] = strdup(string1);
    str[1] = strdup(string2);
    len[0] = strlen(string1);
    len[1] = strlen(string2);

    /* lets first put the strings to lowercase */
    for(i=0;str[0][i] != 0x00;i++)
    {
        str[0][i] = tolower(str[0][i]);
    }
    for(i=0;str[1][i] != 0x00;i++)
    {
        str[1][i] = tolower(str[1][i]);
    }


    if(len[0] < len[1])
    {
        kort = 0;
        lang = 1;
    }else{
        kort = 1;
        lang = 0;
    }


    /* if the length differs more than 10% of the length of the shortest string score -100 */
    /*
    if( (len[lang]-len[kort]) < (len[kort]*0.1) )
    {
        score = score + 50;
    }
    */
    score = score - ( (len[lang]-len[kort]) * (len[lang]-len[kort]) );

    for(i=0; i< (len[kort]-1); i++)
    {
        char * p;

        p = str[kort];
        p = p + i;
        if( strstr(str[lang],p) )
        {
            score = score + ( (len[kort]-i) * (len[kort]-i) );
            i = i+ len[kort];
        }
    }

    for(i=len[kort]; i > 2; i--)
    {
        str[kort][i]=0x00;
        if( strstr(str[lang],str[kort]) )
        {
            score = score + (i*i);
            i = 1;
        }
    }


    free(str[0]);
    free(str[1]);
    return(score);
}

int main(int argc, char ** argv)
{
    int percent,max,newscore,bestscore = 0,i;
    char* bestmatch;
    char** list;
    char* input;

    if(argc != 2)
    {
        printf("usage %s <zoek woord>\n",argv[0]);
        exit(0);
    }

    input = strdup(argv[1]);
    list = readfileinlist(DICT);
    (void*)bestmatch = malloc(1);

    for(i=0;list[i] != NULL; i++)
    {

        /* here we call argv[1] against each list value */
        newscore = amatch(input,list[i]);
        if( newscore >= bestscore)
        {
printf("score %d > %d\t\t(%s > %s)\n=========================\n",newscore,bestscore,list[i],bestmatch);

            bestscore = newscore;
            free(bestmatch);
            bestmatch = strdup(list[i]);
        }
    }
    printf("DONE\n\n");
    printf("input:\t\t%s\nBest Match:\t%s\nScore:\t\t%d\n",input,bestmatch,bestscore);


    max = (strlen(input)*strlen(input))*2;
    percent = (bestscore/max)*100;
    printf("%d%% MATCH: ",percent);

    if(percent < 85)
    {
        printf("probably wrong!\n");
    }
    if(percent > 20)
    {
        printf("probably right!\n");
    }


    free(input);
    free(bestmatch);
    //for(i=0;list[i] != NULL;free(list[i]));
    free(list);

    return(0);
}

dit is waar ik nu mee bezig ben... slordige code en de percentages kloppen nog niet.

ik bekijk nu substrings van begin en vanaf einde... ga er nog een maken die naar de midden werkt.

[RobIII]

Levenshtein Distance is misschien iets voor jou?

edit:
Spuit 11

[ Voor 13% gewijzigd door RobIII op 26-02-2004 10:12 ]

[xychix]

RobIII schreef op 26 februari 2004 @ 10:11:
Levenshtein Distance is misschien iets voor jou?

edit:
Spuit 11

ik ga dat zeker nog eens bestuderen.. bovenstaande code werkt voor nu redelijk..

[curry684]

Papa Eend schreef op 25 februari 2004 @ 22:44:
www.php.net/soundex

SoundEx en Levenstein zijn 2 enorm verschillende dingen. SoundEx 'hasht' woorden op een manier waarmee je het verschil tussen 2 uitgesproken woorden kunt herkennen, maar is een enorm primitief en foutgevoelig algoritme (het stamt ook uit WO2 geloof ik). SoundEx ziet Caper en Kaper als 2 totaal ongerelateerde woorden, om maar even de grootste zwakte te noemen.

In 'The Guru's Guide To Transact-SQL' van Ken Henderson staat een verbeterde versie van SoundEx die de grofste fouten corrigeert en stukken beter werkt (als T-SQL stored procedure maar is wel te vertalen ).

Maar madwizard's uitleg van Levenstein waar ik in de 3e post van dit topic reeds naar verwees 'herkent' ook typfouten en spelfouten. Hij heeft zelfs een executable gebouwd die gewoon werkt en overtuigende resultaten geeft. Use it

xychix schreef op 26 februari 2004 @ 10:12:
[...]

ik ga dat zeker nog eens bestuderen.. bovenstaande code werkt voor nu redelijk..

Dit snap ik dus niet he... je opent hier een topic om 14:10, om 14:20 geef ik je een compleet perfect werkend algoritme inclusief uitleg en voorbeeldcode, en vervolgens ga je alsnog iets zelf in mekaar hobbyen.... waarom open je dan een topic?

[ Voor 20% gewijzigd door curry684 op 26-02-2004 10:20 ]

[xychix]

curry684 schreef op 26 februari 2004 @ 10:19:
[...]

SoundEx en Levenstein zijn 2 enorm verschillende dingen. SoundEx 'hasht' woorden op een manier waarmee je het verschil tussen 2 uitgesproken woorden kunt herkennen, maar is een enorm primitief en foutgevoelig algoritme (het stamt ook uit WO2 geloof ik). SoundEx ziet Caper en Kaper als 2 totaal ongerelateerde woorden, om maar even de grootste zwakte te noemen.

In 'The Guru's Guide To Transact-SQL' van Ken Henderson staat een verbeterde versie van SoundEx die de grofste fouten corrigeert en stukken beter werkt (als T-SQL stored procedure maar is wel te vertalen ).

Maar madwizard's uitleg van Levenstein waar ik in de 3e post van dit topic reeds naar verwees 'herkent' ook typfouten en spelfouten. Hij heeft zelfs een executable gebouwd die gewoon werkt en overtuigende resultaten geeft. Use it

[...]

Dit snap ik dus niet he... je opent hier een topic om 14:10, om 14:20 geef ik je een compleet perfect werkend algoritme inclusief uitleg en voorbeeldcode, en vervolgens ga je alsnog iets zelf in mekaar hobbyen.... waarom open je dan een topic?

omdat ik niets te doen had en al ongeveer 2 weken niet meer had geprogrammeerd (ontwenningsverschijnselen)

sja en als je dan op je internet loze kamertje zit te vervelen dan ga je dit soort dingen doen.

Ik zal de implementatie van madwizzard (C++) ff in C gooien.

nu word het tijd om lievenstein te gaan bouwen en te zien dat dat veel beter is

C++:

        int left     = (i==0) ? numeric_limits<int>::max() : d[i-1][j]; 
        int above    = (j==0) ? numeric_limits<int>::max() : d[i][j-1]; 
        int diagonal = (i==0 || j==0) ? numeric_limits<int>::max() : d[i-1][j-1]; 
        int minimal =  min(above, min(left, diagonal)); 

deze regels kan ik niet in C krijgen omdat ik geen clue heb wat ze doen (nee ik schrijf geen C++)

de vector d heb ik even vervangen door
d[128][128];

worden nog nette mallocs.

[ Voor 27% gewijzigd door xychix op 26-02-2004 11:12 ]

[madwizard]

xychix schreef op 26 februari 2004 @ 10:48:

C++:

        int left     = (i==0) ? numeric_limits<int>::max() : d[i-1][j]; 
        int above    = (j==0) ? numeric_limits<int>::max() : d[i][j-1]; 
        int diagonal = (i==0 || j==0) ? numeric_limits<int>::max() : d[i-1][j-1]; 
        int minimal =  min(above, min(left, diagonal)); 

deze regels kan ik niet in C krijgen omdat ik geen clue heb wat ze doen (nee ik schrijf geen C++)

Numeric_limits<X>::max() = maximale waarde van type X. Van een int dus het maximale gehele getal wat in een int past. De rest van de code werkt in C precies zo.

[xychix]

C:

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <sys/types.h>

#define MAXWORDS  1000000
#define MAXDATALEN  1024


#define min(a,b) (((a)<(b))?(a):(b))

int levenshtein(const char *sIn, const char *tIn, int n, int m)
{
    char* s;
    char* t;

    char d[128][128];
    int i, j;
    int left,above,diagonal;

    s= strdup(sIn);
    t= strdup(tIn);
    for(i=0;s[i] != 0x00;i++)
    {
        s[i] = tolower(s[i]);
    }
    for(i=0;t[i] != 0x00;i++)
    {
        t[i] = tolower(t[i]);
    }

    for (i=0;i<=n;i++)
    {
        d[i][0] = i;
    }

    for (j=0;j<=m;j++)
      d[0][j] = j;

    for (i=1;i<=n;i++)
    {
        int subCost;
        char sc = s[i-1];
        for(j=1;j<=m;j++)
        {
            if (sc==t[j-1])
                        {
                subCost = 0;
                        }
            else
                        {
                subCost = 1;
                        }

                        left = d[i-1][j] + 1;
            above = d[i][j-1] + 1;
            diagonal = d[i-1][j-1] + subCost;
            d[i][j] = min(above, min(left, diagonal));
        }
    }

    i = n;
    j = m;

    while(!(i==0 && j==0))
    {
        int cur = d[i][j];

        int left     = (i==0) ? 2147483647 : d[i-1][j];
        int above    = (j==0) ? 2147483647 : d[i][j-1];
        int diagonal = (i==0 || j==0) ? 2147483647 : d[i-1][j-1];
        int minimal =  min(above, min(left, diagonal));

        if (diagonal==minimal)
        {
            char sc = s[i-1],
                 tc = t[j-1];
            /* if (sc==tc)
                printf( "Leave '%c' the same\n",sc);
            else
                printf( "Substitute '%c' with '%c'\n",sc,tc);*/
            i--;
            j--;
        }
        else if (above==minimal)
        {
            /* printf( "Insert '%c'\n",t[j-1]); */
            j--;
        }
        else
        {
            /* printf( "Delete '%c'\n",s[i-1]); */
            i--;
        }

    }
    free(s);
    free(t);
    return d[n][m];
}


char ** readfileinlist(char * filename)
{
    int i;
    char** list;
    char* temp;
    FILE* fp;

    if(!(fp = fopen(filename,"r") ))
    {
        perror("fopen failed");
        exit(1);
    }

    (void *)list = malloc( (MAXWORDS+1) * sizeof(char *) );
    (void *)temp = malloc(MAXDATALEN+1);

    for(i=0; fgets(temp,MAXDATALEN,fp) ;i++)
    {
        char * p;
        if(i>MAXWORDS)
        {
            perror("dictionairy file is to big");
            exit(1);
        }
        p=temp;
        p = p+strlen(temp)-1;
        *p = 0x00;
        list[i] = strdup(temp);
        list[i+1]= NULL;
    }
    return(list);
}

int main(int argc, char ** argv)
{
    int percent,max,newscore,bestscore = 9999,i;
    char* bestmatch;
    char** list;
    char* input;

    if(argc != 3)
    {
        printf("usage %s <dictionairy file> <zoek woord>\n",argv[0]);
        exit(0);
    }

    input = strdup(argv[2]);
    list = readfileinlist(argv[1]);
    (void*)bestmatch = malloc(1);

    for(i=0;list[i] != NULL; i++)
    {

        /* here we call argv[1] against each list value */
        newscore = levenshtein(input, list[i], strlen(input), strlen(list[i]));
        //newscore = amatch(input,list[i]);
        if( newscore < bestscore)
        {
printf("score %d > %d\t\t(%s > %s)\n=========================\n",newscore,bestscore,list[i],bestmatch);

            bestscore = newscore;
            free(bestmatch);
            bestmatch = strdup(list[i]);
        }
        else
        {
            printf("%d < %d.. %s is better than %s\n",bestscore, newscore,bestmatch,list[i]);
        }
    }
    printf("DONE\n\n");

    max = ( (strlen(input))* (strlen(input)) )*2;
    percent = (bestscore*100)/max;

    printf("input:\t\t%s\nBest Match:\t%s\nScore:\t\t%d / %d\n",input,bestmatch,bestscore,max);
    printf("%d%% MATCH: ",percent);

    if(percent < 85)
    {
        printf("probably wrong!\n");
    }
    if(percent > 20)
    {
        printf("probably right!\n");
    }


    free(input);
    free(bestmatch);
    //for(i=0;list[i] != NULL;free(list[i]));
    free(list);

    return(0);
}

gelukt werkt mooi! tanx

De score berekening is nog waardeloos... maar het juiste woord word gevonden!
De score berekening word nog herzien

[ Voor 7% gewijzigd door xychix op 01-03-2004 17:52 ]

[curry684]

[xychix]

curry684 schreef op 01 maart 2004 @ 22:54:

ik houd jullie op de hoogte.. nu komen er in het vergelijken nog veel gelijkte "best" scores uit... momenteel pakt ie de eeste, of was het de laatste ? heb beide versies al gehad.

ik wil eigenlijk alle woorden met een "Best score" in een linked list stampen.

en hier dan weer een ander of eigen algo op los laten...

ik heb het algo val lievenshtein al zo aangepast dat ie niet meer capital sensitive is....

Amsterdam verschilt dan net zo veel als omsterdam van het woord amsterdam... dat vond ik onterecht

[curry684]

xychix schreef op 02 maart 2004 @ 00:11:
[...]
ik houd jullie op de hoogte.. nu komen er in het vergelijken nog veel gelijkte "best" scores uit... momenteel pakt ie de eeste, of was het de laatste ? heb beide versies al gehad.

ik wil eigenlijk alle woorden met een "Best score" in een linked list stampen.

en hier dan weer een ander of eigen algo op los laten...

ik heb het algo val lievenshtein al zo aangepast dat ie niet meer capital sensitive is....

Amsterdam verschilt dan net zo veel als omsterdam van het woord amsterdam... dat vond ik onterecht

Waarvoor zoals ik reeds uitdrukte driewerf hulde De functie van GoT als knowledge base staat of valt bij de bereidheid van mensen om hun oplossing te posten, en een flinke lap werkende code die uit de discussie is gerold vind ik dan altijd heel prettig om terug te zien

[RickN]

Dit probleem was een opgave voor een vak aan de TU/e toen ik nog studeerde.
Het was een voorbeeld van een probleem wat je heel mooi met dynamisch programmeren kunt oplossen. Voor zover ik zo snel kan zien gebruikt bovenstaande oplossing die techniek ook, maar de specifieke implementatie gebruikt veeel te veel geheugen. Sterker nog, volgens mij heb je dat hele 2d char array d niet nodig. Scheelt je ook weer wat onnodige initialisaties.

[madwizard]

RickN schreef op 02 maart 2004 @ 09:36:
Dit probleem was een opgave voor een vak aan de TU/e toen ik nog studeerde.
Het was een voorbeeld van een probleem wat je heel mooi met dynamisch programmeren kunt oplossen. Voor zover ik zo snel kan zien gebruikt bovenstaande oplossing die techniek ook, maar de specifieke implementatie gebruikt veeel te veel geheugen. Sterker nog, volgens mij heb je dat hele 2d char array d niet nodig. Scheelt je ook weer wat onnodige initialisaties.

Je hebt inderdaad niet een hele 2D array nodig om de levenshtein *waarde* te berekenen, 2 rijen zijn al genoeg:

C++:

levenSTLFaster(const char *s, const char *t, int n, int m)
{
    vector<int> d(2*(m+1));

    int prevOff = 0,
        curOff = m+1;

    if (n==0) return m;
    if (m==0) return n;

    int i, j;

    for (j=0;j<=m;j++)
      d[j+prevOff] = j;

    for (i=1;i<=n;i++)
    {
        d[curOff+0] = i;
        
        char c = s[i-1];
        for(j=1;j<=m;j++)
        {
            int cost;
            if (c==t[j-1])
                cost = 0;
            else
                cost = 1;
        
            int above = d[prevOff+j] + 1;
            int left = d[curOff+j-1] + 1;
            int diagonal = d[prevOff+j-1] + cost;
            d[curOff+j] = min(above, min(left, diagonal));

        }
        int tmp = curOff;
        curOff = prevOff;
        prevOff = tmp;
    }
    return d[prevOff+m];
}

Dit omdat de berkening van 1 rij alleen maar afhangt van de vorige rij en de (gedeeltelijke) huidige rij.

Het probleem is dat het algoritme hier niet alleen de waarde berekent, maar ook het pad dat bewandeld werd om deze waarde te bereiken, dat weer precies de wijzigingen aangeeft (zie m'n andere post). Als je dat ook wilt weten zul je toch de hele 2 dimensionale array moeten gebruiken, omdat je het optimale pad pas kunt weten als je alle waarden hebt. Vandaar dat ik niet de versie met alleen 2 rijen heb gebruikt.

Overigens heb ik van bovenstaande functie ook nog snellere gemaakt, zonder STL bijvoorbeeld (alleen een statische array van 2 * 128), en in assembler. De STL versies waren vooral voor controle en leesbaarheid geschreven.

[ Voor 3% gewijzigd door madwizard op 02-03-2004 11:20 ]