[Zope-Checkins] CVS: Zope/lib/python/Products/PluginIndexes/TextIndexNG/src/PySimilarity/src - Proximity.c:1.1.2.1 levenshtein.c:1.1.2.1 metaphone.c:1.1.2.1 soundex.c:1.1.2.1

Andreas Jung andreas@digicool.com
Thu, 14 Feb 2002 20:07:42 -0500


Update of /cvs-repository/Zope/lib/python/Products/PluginIndexes/TextIndexNG/src/PySimilarity/src
In directory cvs.zope.org:/tmp/cvs-serv10958/PySimilarity/src

Added Files:
      Tag: ajung-textindexng-branch
	Proximity.c levenshtein.c metaphone.c soundex.c 
Log Message:
initial import


=== Added File Zope/lib/python/Products/PluginIndexes/TextIndexNG/src/PySimilarity/src/Proximity.c ===
#include "Python.h"

extern int metaphone(char *word, int max_phonemes, char **phoned_word, int traditional);
extern char * soundex(char *word);
extern int levenshtein(char *word1, char *word2);

static PyObject *
PyAvailableAlgorithms(PyObject *modinfo, PyObject *args)
{
    PyObject *list;

    list = PyList_New(0);

    PyList_Append(list,PyString_FromString("metaphone"));
    PyList_Append(list,PyString_FromString("soundex"));
    PyList_Append(list,PyString_FromString("levenshtein"));

    return list;
}


static PyObject *
PyMetaphone(PyObject *modinfo, PyObject *args)
{

    PyObject *data;
    char * meta;
    int    meta_len = 6;

    if (! (PyArg_ParseTuple(args,"O",&data)))
        return NULL;


    if (PyString_Check(data)) {
        PyObject *encoded;
        char *word;

        word = PyString_AsString(data);

        metaphone(word,meta_len,&meta,0);

        encoded= PyString_FromString(meta);
        free(meta);

        return encoded;

    } else if (PySequence_Check(data)) {

        PyObject * item=NULL,*list=NULL,*encoded=NULL;
        char *word = NULL;
        int i;

        list = PyList_New(0);

        for (i=0; i<PySequence_Size(data);i++) {

            item = PySequence_GetItem(data,i);
            if (!PyString_Check(item)) {

                PyErr_SetString(PyExc_TypeError, "Unsupported datatype found in list (only strings allowed)");
                return NULL;
            }

            word = PyString_AsString(item);

            metaphone(word,meta_len,&meta,0);

            encoded= PyString_FromString(meta);
            free(meta);

            PyList_Append(list, encoded);
            Py_DECREF(encoded);
        }

        return list;

    } else {

        PyErr_SetString(PyExc_TypeError, "Unsupported datatype (must be string or sequence of strings)");

        return NULL;
    }
}



static PyObject *
PySoundex(PyObject *modinfo, PyObject *args)
{
    PyObject *data;

    if (! (PyArg_ParseTuple(args,"O",&data)))
        return NULL;


    if (PyString_Check(data)) {
        PyObject *encoded;
        char * res,*word;

        word = PyString_AsString(data);
        res = soundex(word);

        encoded = PyString_FromString(res);
        free(res);

        return encoded;

    } else if (PySequence_Check(data)) {

        PyObject * item=NULL,*list=NULL,*encoded=NULL;
        char *word = NULL,*res = NULL;
        int i;

        list = PyList_New(0);

        for (i=0; i<PySequence_Size(data);i++) {

            item = PySequence_GetItem(data,i);
            if (!PyString_Check(item)) {

                PyErr_SetString(PyExc_TypeError, "Unsupported datatype found in list (only strings allowed)");
                return NULL;
            }

            word = PyString_AsString(item);

            res = soundex(word);
            encoded = PyString_FromString(res);
            free(res);

            PyList_Append(list, encoded);
            Py_DECREF(encoded);
        }

        return list;

    } else {

        PyErr_SetString(PyExc_TypeError, "Unsupported datatype (must be string or sequence of strings)");

        return NULL;
    }
}


static  PyObject *
PyLevenshtein(PyObject *modinfo, PyObject *args)
{
    PyObject * res=NULL;
    char *word1, *word2;
    int distance;

    if (! (PyArg_ParseTuple(args,"ss",&word1,&word2)))
        return NULL;

    distance = levenshtein(word1,word2);

    res = PyInt_FromLong( (long) distance);
    printf("%d\n",distance); fflush(stdout);

    return res;
}

static struct PyMethodDef Proximity_module_methods[] =
    {
        { "availableAlgorithms", (PyCFunction)PyAvailableAlgorithms,
            METH_VARARGS,
            "availableAlgorithms() "
            "-- return list of available string proximity algorithms"
        },
        { "metaphone", (PyCFunction)PyMetaphone,
          METH_VARARGS,
          "metaphone(word,[encoding_len=6]) "
          "-- return metaphone encoding for word"
        },
        { "soundex", (PyCFunction)PySoundex,
          METH_VARARGS,
          "soundex(word) "
          "-- return soundex encoding for word"
        },
        { "levenshtein", (PyCFunction)PyLevenshtein,
          METH_VARARGS,
          "levenshtein(word1,word2)"
          "-- return computed distances between word1 and word2"
        },
        { NULL, NULL }
    };

static char Proximity_module_documentation[] =
    "Module for string proximity algorithms\n"
    "\n"
    "$Id: Proximity.c,v 1.1.2.1 2002/02/15 01:07:41 andreasjung Exp $\n"
    ;


void
initProximity(void)
{
    PyObject *m, *d;
    char *rev="$Revision: 1.1.2.1 $";

    /* Create the module and add the functions */
    m = Py_InitModule4("Proximity", Proximity_module_methods,
                       Proximity_module_documentation,
                       (PyObject*)NULL,PYTHON_API_VERSION);

    /* Add some symbolic constants to the module */
    d = PyModule_GetDict(m);
    PyDict_SetItemString(d, "__version__",
                         PyString_FromStringAndSize(rev+11,strlen(rev+11)-2));

    if (PyErr_Occurred())
        Py_FatalError("can't initialize module Proximity");
}


=== Added File Zope/lib/python/Products/PluginIndexes/TextIndexNG/src/PySimilarity/src/levenshtein.c ===
#include <stdlib.h>
#include <string.h>

#define LEVENSHTEIN_MAX_LENTH 255


int levenshtein(const char *s1,  const char *s2)

{

    int *p1, *p2, *tmp;
    int i1, i2, c0, c1, c2;

    int l1,l2, cost_ins, cost_rep, cost_del;

    l1 = strlen(s1);
    l2 = strlen(s2);

    cost_ins  = 1;
    cost_rep  = 1;
    cost_del  = 1;


    if(l1==0)
        return l2*cost_ins;
    if(l2==0)
        return l1*cost_del;

    if((l1>LEVENSHTEIN_MAX_LENTH)||(l2>LEVENSHTEIN_MAX_LENTH))
        return -1;

    if(!(p1=malloc(l2*sizeof(int)))) {
        return -2;
    }
    if(!(p2=malloc(l2*sizeof(int)))) {
        free(p1);
        return -2;
    }

    p1[0]=(s1[0]==s2[0])?0:cost_rep;

    for(i2=1;i2<l2;i2++)
        p1[i2]=i2*cost_ins;

    for(i1=1;i1<l1;i1++) {
        p2[0]=i1*cost_del;
        for(i2=1;i2<l2;i2++) {
            c0=p1[i2-1]+((s1[i1]==s2[i2])?0:cost_rep);
            c1=p1[i2]+cost_del;
            if(c1<c0)
                c0=c1;
            c2=p2[i2-1]+cost_ins;
            if(c2<c0)
                c0=c2;
            p2[i2]=c0;
        }
        tmp=p1;
        p1=p2;
        p2=tmp;
    }

    c0=p1[l2-1];

    free(p1);
    free(p2);

    return c0;
}
/* }}} */


=== Added File Zope/lib/python/Products/PluginIndexes/TextIndexNG/src/PySimilarity/src/metaphone.c ===
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

/*
    Based on CPANs "Text-Metaphone-1.96" by Michael G Schwern <schwern@pobox.com>
    and also
    PHP's ext/standard/metaphone.c (See www.php.net for more info)
*/


#define  SH 	'X'
#define  TH		'0'

char _codes[26] =
    {
        1, 16, 4, 16, 9, 2, 4, 16, 9, 2, 0, 2, 2, 2, 1, 4, 0, 2, 4, 4, 1, 0, 0, 0, 8, 0
        /*  a  b c  d e f g  h i j k l m n o p q r s t u v w x y z */
    };


#define ENCODE(c) (isalpha(c) ? _codes[((toupper(c)) - 'A')] : 0)

#define isvowel(c)  (ENCODE(c) & 1)		/* AEIOU */

/* These letters are passed through unchanged */
#define NOCHANGE(c) (ENCODE(c) & 2)		/* FJMNR */

/* These form dipthongs when preceding H */
#define AFFECTH(c)  (ENCODE(c) & 4)		/* CGPST */

/* These make C and G soft */
#define MAKESOFT(c) (ENCODE(c) & 8)		/* EIY */

/* These prevent GH from becoming F */
#define NOGHTOF(c)  (ENCODE(c) & 16)	/* BDH */
/*----------------------------- */
/* end of "metachar.h"          */
/*----------------------------- */

/* I suppose I could have been using a character pointer instead of
 * accesssing the array directly... */

/* Look at the next letter in the word */
#define Next_Letter (toupper(word[w_idx+1]))
/* Look at the current letter in the word */
#define Curr_Letter (toupper(word[w_idx]))
/* Go N letters back. */
#define Look_Back_Letter(n)	(w_idx >= n ? toupper(word[w_idx-n]) : '\0')
/* Previous letter.  I dunno, should this return null on failure? */
#define Prev_Letter (Look_Back_Letter(1))
/* Look two letters down.  It makes sure you don't walk off the string. */
#define After_Next_Letter	(Next_Letter != '\0' ? toupper(word[w_idx+2]) \
											     : '\0')
#define Look_Ahead_Letter(n) (toupper(Lookahead(word+w_idx, n)))


/* Allows us to safely look ahead an arbitrary # of letters */
/* I probably could have just used strlen... */
static char Lookahead(char *word, int how_far)
{
    char letter_ahead = '\0';	/* null by default */
    int idx;
    for (idx = 0; word[idx] != '\0' && idx < how_far; idx++)
        ;
    /* Edge forward in the string... */

    letter_ahead = word[idx];	/* idx will be either == to how_far or
                							 * at the end of the string
                							 */
    return letter_ahead;
}


/* phonize one letter */
#define Phonize(c)	{(*phoned_word)[p_idx++] = c;}
/* Slap a null character on the end of the phoned word */
#define End_Phoned_Word	{(*phoned_word)[p_idx] = '\0';}
/* How long is the phoned word? */
#define Phone_Len	(p_idx)

/* Note is a letter is a 'break' in the word */
#define Isbreak(c)  (!isalpha(c))

/* {{{ metaphone
 */
int metaphone(char *word, int max_phonemes, char **phoned_word, int traditional)
{
    int w_idx = 0;				/* point in the phonization we're at. */
    int p_idx = 0;				/* end of the phoned phrase */

    /*-- Parameter checks --*/
    /* Negative phoneme length is meaningless */

    if (max_phonemes < 0)
        return -1;

    /* Empty/null string is meaningless */
    /* Overly paranoid */
    /* assert(word != NULL && word[0] != '\0'); */

    if (word == NULL)
        return -1;

    /*-- Allocate memory for our phoned_phrase --*/
    if (max_phonemes == 0) {	/* Assume largest possible */
        *phoned_word = (char *) malloc(sizeof(char) * strlen(word) + 1);
        if (!*phoned_word)
            return -1;
    } else {
        *phoned_word = (char *) malloc(sizeof(char) * max_phonemes + 1);
        if (!*phoned_word)
            return -1;
    }


    /*-- The first phoneme has to be processed specially. --*/
    /* Find our first letter */
    for (; !isalpha(Curr_Letter); w_idx++) {
        /* On the off chance we were given nothing but crap... */
        if (Curr_Letter == '\0') {
            End_Phoned_Word
            return 1;	/* For testing */
        }
    }

    switch (Curr_Letter) {
        /* AE becomes E */
    case 'A':
        if (Next_Letter == 'E') {
            Phonize('E');
            w_idx += 2;
        }
        /* Remember, preserve vowels at the beginning */
        else {
            Phonize('A');
            w_idx++;
        }
        break;
        /* [GKP]N becomes N */
    case 'G':
    case 'K':
    case 'P':
        if (Next_Letter == 'N') {
            Phonize('N');
            w_idx += 2;
        }
        break;
        /* WH becomes H,
           WR becomes R 
           W if followed by a vowel */
    case 'W':
        if (Next_Letter == 'H' ||
                Next_Letter == 'R') {
            Phonize(Next_Letter);
            w_idx += 2;
        } else if (isvowel(Next_Letter)) {
            Phonize('W');
            w_idx += 2;
        }
        /* else ignore */
        break;
        /* X becomes S */
    case 'X':
        Phonize('S');
        w_idx++;
        break;
        /* Vowels are kept */
        /* We did A already
           case 'A':
           case 'a':
         */
    case 'E':
    case 'I':
    case 'O':
    case 'U':
        Phonize(Curr_Letter);
        w_idx++;
        break;
    default:
        /* do nothing */
        break;
    }



    /* On to the metaphoning */
    for (; Curr_Letter != '\0' &&
            (max_phonemes == 0 || Phone_Len < max_phonemes);
            w_idx++) {
        /* How many letters to skip because an eariler encoding handled
         * multiple letters */
        unsigned short int skip_letter = 0;


        /* THOUGHT:  It would be nice if, rather than having things like...
         * well, SCI.  For SCI you encode the S, then have to remember
         * to skip the C.  So the phonome SCI invades both S and C.  It would
         * be better, IMHO, to skip the C from the S part of the encoding.
         * Hell, I'm trying it.
         */

        /* Ignore non-alphas */
        if (!isalpha(Curr_Letter))
            continue;

        /* Drop duplicates, except CC */
        if (Curr_Letter == Prev_Letter &&
                Curr_Letter != 'C')
            continue;

        switch (Curr_Letter) {
            /* B -> B unless in MB */
        case 'B':
            if (Prev_Letter != 'M')
                Phonize('B');
            break;
            /* 'sh' if -CIA- or -CH, but not SCH, except SCHW.
             * (SCHW is handled in S)
             *  S if -CI-, -CE- or -CY-
             *  dropped if -SCI-, SCE-, -SCY- (handed in S)
             *  else K
             */
        case 'C':
            if (MAKESOFT(Next_Letter)) {	/* C[IEY] */
                if (After_Next_Letter == 'A' &&
                        Next_Letter == 'I') {	/* CIA */
                    Phonize(SH);
                }
                /* SC[IEY] */
                else if (Prev_Letter == 'S') {
                    /* Dropped */
                } else {
                    Phonize('S');
                }
            } else if (Next_Letter == 'H') {
                if ((!traditional) && (After_Next_Letter == 'R' || Prev_Letter == 'S')) {	/* Christ, School */
                    Phonize('K');
                } else {
                    Phonize(SH);
                }
                skip_letter++;
            } else {
                Phonize('K');
            }
            break;
            /* J if in -DGE-, -DGI- or -DGY-
             * else T
             */
        case 'D':
            if (Next_Letter == 'G' &&
                    MAKESOFT(After_Next_Letter)) {
                Phonize('J');
                skip_letter++;
            } else
                Phonize('T');
            break;
            /* F if in -GH and not B--GH, D--GH, -H--GH, -H---GH
             * else dropped if -GNED, -GN, 
             * else dropped if -DGE-, -DGI- or -DGY- (handled in D)
             * else J if in -GE-, -GI, -GY and not GG
             * else K
             */
        case 'G':
            if (Next_Letter == 'H') {
                if (!(NOGHTOF(Look_Back_Letter(3)) ||
                        Look_Back_Letter(4) == 'H')) {
                    Phonize('F');
                    skip_letter++;
                } else {
                    /* silent */
                }
            } else if (Next_Letter == 'N') {
                if (Isbreak(After_Next_Letter) ||
                        (After_Next_Letter == 'E' &&
                         Look_Ahead_Letter(3) == 'D')) {
                    /* dropped */
                } else
                    Phonize('K');
            } else if (MAKESOFT(Next_Letter) &&
                       Prev_Letter != 'G') {
                Phonize('J');
            } else {
                Phonize('K');
            }
            break;
            /* H if before a vowel and not after C,G,P,S,T */
        case 'H':
            if (isvowel(Next_Letter) &&
                    !AFFECTH(Prev_Letter))
                Phonize('H');
            break;
            /* dropped if after C
             * else K
             */
        case 'K':
            if (Prev_Letter != 'C')
                Phonize('K');
            break;
            /* F if before H
             * else P
             */
        case 'P':
            if (Next_Letter == 'H') {
                Phonize('F');
            } else {
                Phonize('P');
            }
            break;
            /* K
             */
        case 'Q':
            Phonize('K');
            break;
            /* 'sh' in -SH-, -SIO- or -SIA- or -SCHW-
             * else S
             */
        case 'S':
            if (Next_Letter == 'I' &&
                    (After_Next_Letter == 'O' ||
                     After_Next_Letter == 'A')) {
                Phonize(SH);
            } else if (Next_Letter == 'H') {
                Phonize(SH);
                skip_letter++;
            } else if ((!traditional) && (Next_Letter == 'C' && Look_Ahead_Letter(2) == 'H' && Look_Ahead_Letter(3) == 'W')) {
                Phonize(SH);
                skip_letter += 2;
            } else {
                Phonize('S');
            }
            break;
            /* 'sh' in -TIA- or -TIO-
             * else 'th' before H
             * else T
             */
        case 'T':
            if (Next_Letter == 'I' &&
                    (After_Next_Letter == 'O' ||
                     After_Next_Letter == 'A')) {
                Phonize(SH);
            } else if (Next_Letter == 'H') {
                Phonize(TH);
                skip_letter++;
            } else {
                Phonize('T');
            }
            break;
            /* F */
        case 'V':
            Phonize('F');
            break;
            /* W before a vowel, else dropped */
        case 'W':
            if (isvowel(Next_Letter))
                Phonize('W');
            break;
            /* KS */
        case 'X':
            Phonize('K');
            Phonize('S');
            break;
            /* Y if followed by a vowel */
        case 'Y':
            if (isvowel(Next_Letter))
                Phonize('Y');
            break;
            /* S */
        case 'Z':
            Phonize('S');
            break;
            /* No transformation */
        case 'F':
        case 'J':
        case 'L':
        case 'M':
        case 'N':
        case 'R':
            Phonize(Curr_Letter);
            break;
        default:
            /* nothing */
            break;
        }						/* END SWITCH */

        w_idx += skip_letter;
    }							/* END FOR */

    End_Phoned_Word;

    return 0;
}


=== Added File Zope/lib/python/Products/PluginIndexes/TextIndexNG/src/PySimilarity/src/soundex.c ===
#include <stdlib.h>
#include <errno.h>
#include <string.h>
#include <ctype.h>

/* 
    Simple soundex algorithm as described by Knuth in TAOCP, vol 3
    implementation details borrowed from PHP's ext/standard/soundex.c
    (See www.php.net for more info)
*/



char * soundex(char *somestring)
{
    int	i, _small, len, code, last;
    char	 * soundex;

    static char soundex_table[26] =
        {0,							/* A */
         '1',						/* B */
         '2',						/* C */
         '3',						/* D */
         0,							/* E */
         '1',						/* F */
         '2',						/* G */
         0,							/* H */
         0,							/* I */
         '2',						/* J */
         '2',						/* K */
         '4',						/* L */
         '5',						/* M */
         '5',						/* N */
         0,							/* O */
         '1',						/* P */
         '2',						/* Q */
         '6',						/* R */
         '2',						/* S */
         '3',						/* T */
         0,							/* U */
         '1',						/* V */
         0,							/* W */
         '2',						/* X */
         0,							/* Y */
         '2'};						/* Z */

    len = strlen(somestring);
    soundex = (char *) malloc(10);

    /* build soundex string */
    last = -1;
    for (i = 0, _small = 0; i < len && _small < 4; i++) {

        /* convert chars to upper case and strip non-letter chars */
        /* BUG: should also map here accented letters used in non */
        /* English words or names (also found in English text!): */
        /* esstsett, thorn, n-tilde, c-cedilla, s-caron, ... */

        code = toupper(somestring[i]);
        if (code >= 'A' && code <= 'Z') {
            if (_small == 0) {
                /* remember first valid char */
                soundex[_small++] = code;
                last = soundex_table[code - 'A'];
            } else {
                /* ignore sequences of consonants with same soundex */
                /* code in trail, and vowels unless they separate */
                /* consonant letters */
                code = soundex_table[code - 'A'];
                if (code != last) {
                    if (code != 0) {
                        soundex[_small++] = code;
                    }
                    last = code;
                }
            }
        }
    }

    /* pad with '0' and terminate with 0 ;-) */

    while (_small < 4) {
        soundex[_small++] = '0';
    }
    soundex[_small] = '\0';

    return soundex;
}