[INC] FuzzyWords ( soundex / metaphone / levenshtein )

[Destro]

Glosario
- Soundex
- Metaphone
- Levenshtein
- Damerau Levenshtein
- Fuzzy Matching

En estos días estuve estudiando diferentes métodos para crear un SpellChecker(corrector ortográfico).
Cuando empecé a buscar sobre el tema, lo primero que me encontré fue sobre Fuzzy-Matching / Fuzzy-Text, lo que me llevo al algoritmo de Levenshtein.
Con eso ya se podría crear un spellchecker básico, pero tiene un gran problema, no tiene escalabilidad. Si bien podría funcionar correctamente para un diccionario con cientos de palabras, funcionaria fatal al tener miles o decenas de miles de palabras.
Buscando me encontré con muchas soluciones, algunas muy complejas pero con mucha precisión, pero esos métodos suelen consumir mucha memoria RAM al crear muchas Tries/Hashtables. Al final opte por el método mas simple, pre-filtrar las palabras con Soundex / Metaphone.


Funciones:

Código PHP:

// Remueve los acentos y Ñ, pone todo en mayúscula
stock word_normalize(const in[], out[], len)

// https://es.wikipedia.org/wiki/Soundex
// https://es.wikipedia.org/wiki/Metaphone
stock metaphoneES(const word[], out[], len, stripVowel=true)

// https://es.wikipedia.org/wiki/Distancia_de_Damerau-Levenshtein
stock damerau_levenshtein(const string1[], const string2[], w=1, s=1, a=1, d=1)

// https://es.wikipedia.org/wiki/Distancia_de_Levenshtein
stock levenshtein(const string1[], const string2[]) 


Ejemplo:

Código PHP:

#include <amxmodx>
#include <fuzzywords>

#define DEBUG_ENABLE
#include <debug>


#define PLUGIN    "Basic SpellChecker"
#define VERSION "1.0"
#define AUTHOR    "Destro"


new Trie:g_TrieDict

enum _:_EntryStruct
{
    Entry_Original[32],
    Entry_Normalize[32],    // Second Search
    Entry_Soundex[32],        // First Search
    Entry_Freq                // Frequency
}

public plugin_init()
{
    // Para encontrar el error de un crash, lo mejor es tener control sobre el inicio y la finalización de las funciones publicas
    // Una vez que detectas en cual public esta el problema, lo demás es mas fácil
    debug_hidden("plugin_init() PRE")

    register_plugin(PLUGIN, VERSION, AUTHOR)
    
    register_srvcmd("sc", "svcmd_spellcheck")

    set_task(2.0, "task_delay")

    debug_hidden("plugin_init() POST")
}

public plugin_end()
{
    debug_hidden("plugin_end() PRE")

    TrieDestroy(g_TrieDict)

    debug_hidden("plugin_end() POST")

    // Depende del tipo de crash, puede o no llamarse a plugin_end()
    // Si no se llama, vas a tener que considerar en usar #define DEBUG_ONLY_LOGS
    // Pero trata de no loggear funciones que se llamen decenas de veces por segundo, sino matas al disco
    debug_end()
}

public task_delay()
{
    debug_hidden("task_delay() PRE")


    // Veamos cuanto tiempo tarda en cargar el diccionario...
    debug_performance_start(hola)
    load_dictionary()
    debug_performance_end(hola, "load_dictionary()")


    debug_hidden("task_delay() POST")
}

load_dictionary()
{
    new entry[_EntryStruct], Array:a, f
    g_TrieDict = TrieCreate()

    f = fopen("es-AR.dic", "r")
    if(!f)
    {
        debug_log1("Error al cargar el diccionario")
        return
    }

    new maxrepeat, maxrepeatKey[32] 

    while(!feof(f))
    {
        fgets(f, entry[Entry_Original], 31)

        trim(entry[Entry_Original])

        word_normalize(entry[Entry_Original], entry[Entry_Normalize], 31)
        metaphoneES(entry[Entry_Original], entry[Entry_Soundex], 31)


        if(TrieKeyExists(g_TrieDict, entry[Entry_Soundex]))
        {
            TrieGetCell(g_TrieDict, entry[Entry_Soundex], a)
            ArrayPushArray(a, entry)

            if(ArraySize(a) > maxrepeat)
            {
                copy(maxrepeatKey, 31, entry[Entry_Soundex])
                maxrepeat = ArraySize(a)
            }
        }
        else {
            a = ArrayCreate(_EntryStruct, 1)

            ArrayPushArray(a, entry)
            TrieSetCell(g_TrieDict, entry[Entry_Soundex], a)
        }

    }

    fclose(f)

    debug_log1("dictionary max repeat metaphone: %d - %d", maxrepeat, maxrepeatKey)
}

public svcmd_spellcheck()
{
    debug_hidden("svcmd_spellcheck() PRE")

    new input[32], soundkey[32], normalize[32]

    read_argv(1, input, 31)

    word_normalize(input, normalize, 41)
    metaphoneES(normalize, soundkey, 31)


    if(TrieKeyExists(g_TrieDict, soundkey))
    {
        server_print("Sugerencias para: ^"%s^" (%s) -> [%s] :", input, normalize, soundkey)

        new entry[_EntryStruct], Array:a

        TrieGetCell(g_TrieDict, soundkey, a)

        new size = ArraySize(a)

        debug_performance_start(sort)
        ArraySort(a, "ArraySortResult", normalize, 31)
        debug_performance_end(sort,"ArraySortResult")

        for(new i; i < size; i++)
        {
            ArrayGetArray(a, i, entry)

            new soundes[36]
            metaphoneES(entry[Entry_Original], soundes, 35, false)

            server_print("- %s ^t%s  ^t->  [%s]", entry[Entry_Original], entry[Entry_Normalize], entry[Entry_Soundex])
        }

        server_print("^n")
        debug_hidden("svcmd_spellcheck() POST")
        return
    }

    server_print("No se encontro  [%s]^n", soundkey)
    debug_hidden("svcmd_spellcheck() POST")
}

public ArraySortResult(Array:a, item1, item2, const normalize[])
{
    static data1[_EntryStruct], data2[_EntryStruct]

    ArrayGetArray(a, item1, data1)
    ArrayGetArray(a, item2, data2)

    new distance1 = damerau_levenshtein(data1[Entry_Normalize], normalize)
    new distance2 = damerau_levenshtein(data2[Entry_Normalize], normalize)

    if(distance1 < distance2)
        return -1
    if(distance1 > distance2)
        return 1

    if(data1[Entry_Freq] < data2[Entry_Freq])
        return -1
    if(data1[Entry_Freq] > data2[Entry_Freq])
        return 1

    return 0
} 


  fuzzywords.inc (Tamaño: 6.36 KB / Descargas: 16)

[Valentina.]

Excelente aporte Destro; un capo.

[SoundBlaster]

Interesante aporte

[+rdNN!]

Buen aporte !, deberías dejar una información para que sirve para algunos usuarios novatos en eso me incluyo.

[Pablo_1998]

Good Job!

[Federicomb]

Esta interesante el aporte, cuando esté en la PC lo voy a ver con más comodidad porque en el celu se deforma todo XD.

Por lo rápido que ví, estaría bueno que le des soporte para amx 1.9 y uses algunas de las funciones nuevas que tiene que están mejor optimizadas. O mejor aún, quizás puedas aportarlo para que sea parte de amx

[totopizza]

Buen aporte destro

Estaba revisando el inc, y vi esto:

Código PHP:

replace_all(buff, charsmax(buff), "MN", "N") 


Que pasa con las palabras que llevan "mn"?
columna, amnesia, insomnio, alumno, somnolencia?



PD: No lo he probado todavia

[Destro]

Esta interesante el aporte, cuando esté en la PC lo voy a ver con más comodidad porque en el celu se deforma todo XD.

Por lo rápido que ví, estaría bueno que le des soporte para amx 1.9 y uses algunas de las funciones nuevas que tiene que están mejor optimizadas. O mejor aún, quizás puedas aportarlo para que sea parte de amx

ya me tendría que estar actualizandome, todavía tengo amxx 1.8.1 y 1.8.2 xd

Buen aporte destro

Estaba revisando el inc, y vi esto:

Código PHP:

replace_all(buff, charsmax(buff), "MN", "N") 


Que pasa con las palabras que llevan "mn"?
columna, amnesia, insomnio, alumno, somnolencia?



PD: No lo he probado todavia

en esos casos la M suena algo similar a la N, es como CE CI S Z X que tienen casos en los que suenan muy similares

"amnesia" queda en "anesia", el metaphone es "ANS"

[KrR10VnZl]

Buen aporte!

[totopizza]

Esta interesante el aporte, cuando esté en la PC lo voy a ver con más comodidad porque en el celu se deforma todo XD.

Por lo rápido que ví, estaría bueno que le des soporte para amx 1.9 y uses algunas de las funciones nuevas que tiene que están mejor optimizadas. O mejor aún, quizás puedas aportarlo para que sea parte de amx

ya me tendría que estar actualizandome, todavía tengo amxx 1.8.1 y 1.8.2 xd

Buen aporte destro

Estaba revisando el inc, y vi esto:

Código PHP:

replace_all(buff, charsmax(buff), "MN", "N") 


Que pasa con las palabras que llevan "mn"?
columna, amnesia, insomnio, alumno, somnolencia?



PD: No lo he probado todavia

en esos casos la M suena algo similar a la N, es como CE CI S Z X que tienen casos en los que suenan muy similares

"amnesia" queda en "anesia", el metaphone es "ANS"

Ok

[Destro]

recién me doy cuenta de que esta bug el compiler, convierte mal los caracteres UTF cuando están en un include :S
voy a tener que escribir los bits manualmente, shit

_________
@Edit
Listo, corregido y agregado un plugin de ejemplo

[OsweRRR]

recién me doy cuenta de que esta bug el compiler, convierte mal los caracteres UTF cuando están en un include :S
voy a tener que escribir los bits manualmente, shit

_________
@Edit
Listo, corregido y agregado un plugin de ejemplo

creo que revirtieron algo que habían hecho.

https://github.com/alliedmodders/amxmodx...982102f138

[[MxE]M4T4D0'R DJ's]

Yo hace unas semanas estaba intentando lo mismo x.x, si me acuerdo dejare mi base por aquí.

Pd: Muy buen aporte.

Saludos

[Skylar]

Excelente aporte Destro; un capo.