Skip to Content.
Sympa Menu

pcplantdb - Re: [pcplantdb] Eden 0.1.3 release - testing search again

pcplantdb@lists.ibiblio.org

Subject: pcplantdb

List archive

Chronological Thread  
  • From: Richard Morris <webmaster@pfaf.org>
  • To: Permaculture Plant Database <pcplantdb@lists.ibiblio.org>
  • Subject: Re: [pcplantdb] Eden 0.1.3 release - testing search again
  • Date: Fri, 24 Dec 2004 10:35:47 +0000

Lawrence F. London, Jr. wrote:
Chad Knepp wrote:

Well, I can think of a couple of reasons. Elaeagnus has an 'a' in it
that I forget a lot myself. Eden does accommodate 'alternative'

Spelling of latin names is a big issue.
The way I've handled this is to put every concievable spelling as a synonym.

In particular there are alternate suffixes used in the plant names
different database use different ending for example:
Acanthopanax ricinifolius
Acanthopanax ricinifolium

Acanthopanax spinosum
Acanthopanax spinosus

Achillea millefolia
Achillea millefolium

this is all to do with the three genders in latin, male, female and neuter.
In general the tuples (us,um,a), (is,e), (ica,iana), (um,on)
represent different endings for different genders, memebers of each tuple are considered equivilent ending.
Also there are cases like "ii" which is often written "i"
(ae,a), (ea,a), (y,i), (ll,l), (sch,sh), (nn,n), (tt,t), (io,o)
are considered equivilent anywhere in the name.


I've a perl script "cspelling.pl" which looks for known changes in suffixes
and a c program "fuzmatch.c" which looks at small changes in spelling
for instance if a single character is added or deleated
or the order of two characters is reversed.

The general approach has been to compile lists of all know
spellings and spellings in pfaf db.
Then run fuzmatch which find small changes and labels them
"A1" for add one character etc.
Then run cspelling.pl which picks out know suffix changes
i.e. suffixes above.

This procedure finds some incorrect matches which are later removed.

Source code is attached, feel free to adapt and modify at will.

Festive greeting to all

Rich

--
Plants for a Future: 7000 useful plants
Web: http://www.pfaf.org/ same as http://www.comp.leeds.ac.uk/pfaf/
Post: 1 Lerryn View, Lerryn, Lostwithiel, Cornwall, PL22 0QJ
Tel: 01208 872 963 / 0845 458 4719
Email: webmaster@pfaf.org
PFAF electronic mailing list http://groups.yahoo.com/group/pfaf

/*
* reads in two files and prints out
* fuzzy matches of names
* i.e. if only one character has been added/deleted/changed
* fuzmatch pfafsym.txt othersym.txt Y/N
* Y/N determins type of format
*/

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

#define MAX_LENGTH 50
#define NO_MATCH 0
#define EXACT_MATCH 1
#define CNG_ONE 2
#define ADD_ONE 3
#define DEL_ONE 4
#define CNG_TWO 5
#define ADD_TWO 6
#define DEL_TWO 7
#define ADD_ONE_CNG_ONE 8
#define ADD_ONE_DEL_ONE 9
#define DEL_ONE_CNG_ONE 10
#define SUFFIX 11

typedef struct wlist
{
char *text,*dup;
int len,dup_len;
struct wlist* next;
} Wlist;

Wlist *Wadd(Wlist *base,char *text,char *dup)
{
Wlist *ele;

ele = (Wlist *) malloc(sizeof(Wlist));
ele->next = base;
ele->len = strlen(text);
ele->text = strdup(text);
ele->dup_len = strlen(dup);
ele->dup = strdup(dup);
return(ele);
}

int fuzzy_match(char *str1,int len1,char *str2,int len2,int *pos1,int *pos2)
{
int count,i,j,missed_char,missed_char2;

*pos1 = *pos2 = 0;
if(str1[0]!=str2[0]) return(NO_MATCH);

/* first find suffix's *a = *us = *um *i = *ii */

/* if( (len1 == len2 ) && str1[len1-1] == 'u' && str2[len1-1] == 'u'
&& ( ( str1[len] == 'm' && str1[len] ==
*/
if(len1 == len2)
{
/*
printf("LEN1==LEN2 test\n");
*/
count = 0; missed_char = -1; missed_char2 = -1;
for(i=0;i<len1;++i)
{
if(str1[i] == str2[i]) ++count;
else if(missed_char < 0) missed_char = i;
else if(missed_char2 <0) missed_char2 = i;
else break;
}
if(count == len1) return(EXACT_MATCH);
if(count == len1-1)
{
*pos1 = missed_char;
if( missed_char == len1
&& str1[len1-1] == 'u'
&& ( ( str1[len1] == 'm' && str2[len1] == 's' )
||( str1[len1] == 's' && str2[len1] == 'm' ) ) )
return(SUFFIX);


return(CNG_ONE);
}
if(count == len1-2) { *pos1 = missed_char; *pos2 =
missed_char2; return(CNG_TWO); }
return(NO_MATCH); /* what about add_one_del_one */
}


if(len1 == len2-1)
{
/*
printf("LEN1==LEN2-1 test\n");
*/
count = 0; missed_char = -1; missed_char2 = -1;
for(i=0;i<len2;++i)
{
count = 0; missed_char = -1; missed_char2 = -1;
for(j=0;j<i;++j)
{
if(str1[j] == str2[j]) ++count;
else if(missed_char2 <0) missed_char2 = j;
else break;
}
if(count<i-1) break;
for(j=i+1;j<len2;++j)
{
if(str1[j-1] == str2[j]) ++count;
else if(missed_char2 <0) missed_char2 = j;
else break;
}

if(count == len1)
{
*pos1 = i;
return(ADD_ONE);
}
else if(count == len1-1)
{
*pos1 = i;
*pos2 = missed_char2;
/*
printf("len1 %d len2 %d count %d i %d\n",len1,len2,count,i);
*/
return(ADD_ONE_CNG_ONE);
}
}
return(NO_MATCH);
}

if(len1 == len2+1)
{
count = 0; missed_char = -1; missed_char2 = -1;
for(i=0;i<len1;++i)
{
count = 0;
for(j=0;j<i;++j)
{
if(str1[j] == str2[j]) ++count;
else if(missed_char2 <0) missed_char2 = j;
else break;
}
if(count<i-1) break;
for(j=i+1;j<len1;++j)
{
if(str1[j] == str2[j-1]) ++count;
else if(missed_char2 <0) missed_char2 = j;
else break;
}
if(count == len2)
{
*pos1 = i;
return(DEL_ONE);
}
else if(count == len2-1)
{
*pos1 = i;
*pos2 = missed_char2;
return(DEL_ONE_CNG_ONE);
}
}
return(NO_MATCH);
}
/* what about ADD_TWO DEL_TWO */
return(NO_MATCH);
}

/*
* removes special string from a word
* works in place
* if global is true do it repeatedly
*/

remove_special(char *str,char *special,int str_len,int spec_len,int global)
{
char *pos,*pos2;

while(1)
{
pos = strstr(str,special);

if(pos == NULL) break;

/* now modify */

for(pos2 = pos;pos2 <= str + str_len-spec_len;++pos2)
{
*pos2 = *(pos2+spec_len);
/*
printf("str %p pos %p pos2 %p p2+sl %p %s\n",
str,pos,pos2,pos2+spec_len,str);
*/
}

if(!global) break;
}
}

/* substitute specials */

substitute_special(char *str,char *special,char *sub,
int str_len,int spec_len,int sub_len,int global)
{
char *pos,*pos2;
int i;

while(1)
{
pos = strstr(str,special);

if(pos == NULL) break;

/* now modify */

for(i=0;i<sub_len;++i)
{
pos2 = pos+i;
*pos2 = *(sub+i);
}

for(pos2 = pos+sub_len;pos2 <= str +
str_len-spec_len+sub_len;++pos2)
{
*pos2 = *(pos2+spec_len-sub_len);
/*
printf("str %p pos %p pos2 %p p2+sl %p %s\n",
str,pos,pos2,pos2+spec_len,str);
*/
}

if(!global) break;
}
}

remove_all_specials(char *buf,int len)
{
/*
printf("ORIG %s\t",buf);
*/
remove_special(buf," var.",len,5,0);
remove_special(buf," f.",len,3,0);
remove_special(buf," subsp.",len,7,0);
remove_special(buf," ssp.",len,5,0);
remove_special(buf," auct. non",len,10,0);
remove_special(buf," auct. p.p. non",len,15,0);
remove_special(buf," sensu lato",len,11,0);
remove_special(buf,"-",len,1,1);
remove_special(buf,":",len,1,1);
remove_special(buf,"(*)",len,3,1);
substitute_special(buf," x "," X ",len,3,3,0);
/*
printf("REP %s\n",buf);
*/
}

main(int argc,char **argv)
{
char *file1,*file2;
FILE *fp,*fq;
Wlist *base,*ele;
char buf[MAX_LENGTH],buf_dup[MAX_LENGTH],diff[MAX_LENGTH];
int len,res,pos1=0,pos2=0,count=0;
char *format;
int EXACT=0,C1=0,A1=0,D1=0,C2=0,A2=0,D2=0,A1D1=0,A1C1=0,D1C1=0;

base = NULL;
for(len=0;len<MAX_LENGTH-1;++len)
diff[len] = ' ';
diff[len] = '\0';

if(argc!=3&&argc!=4)
{
fprintf(stderr,"Syntax: fuzmatch file1 file2 [Y/N]\n");
exit(1);
}

file1 = strdup(argv[1]);
file2 = strdup(argv[2]);
if(argc==4 && argv[3][0] == 'Y')
format = "\"%s\",\"%s\",\"%s\",\"%s\",\"%s\",\"%s\"\n";
else
{
format = "%s\t%s\n\t%s\n\t%s\n\t%s\n\t%s\n";
}
/*
printf(format,"Type","PFAF short","OTHER","PFAF","Other
short","Diff");
*/
printf(format,"Type","Other","PFAF","Other short","PFAF
Short","Diff");



fp = fopen(file1,"r");
if(fp == NULL )
{
fprintf(stderr,"Could not open %s\n",file1);
}
fq = fopen(file2,"r");
if(fq == NULL )
{
fprintf(stderr,"Could not open %s\n",file2);
}

/* now read in file1 */

while( fgets(buf,MAX_LENGTH,fp) != NULL)
{
len = strlen(buf);
buf[len-1]='\0';
strcpy(buf_dup,buf);
remove_all_specials(buf_dup,len);
base = Wadd(base,buf,buf_dup);
}
fclose(fp);

/* and then the second file */

fprintf(stderr,"Now file2\n");

while( fgets(buf,MAX_LENGTH,fq) != NULL)
{
len = strlen(buf);
buf[len-1]='\0';
--len;
strcpy(buf_dup,buf);
remove_all_specials(buf_dup,len);
len = strlen(buf_dup);

/*
printf("GOT %s\n",buf_dup);
*/
ele = base;
while(ele!=NULL)
{
/*
printf("TEST %s\n",ele->dup);
*/
pos1 = pos2 = 0;
res =
fuzzy_match(buf_dup,len,ele->dup,ele->dup_len,&pos1,&pos2);

if(pos1 < 0 || pos1 > 50 || pos2 < 0 || pos2 > 50) printf("TEST %s pos1 %d
pos2 %d res %d\n",ele->dup,pos1,pos2,res);

diff[pos1] = diff[pos2] = '^';
diff[0] = ' ';
switch(res)
{
case EXACT_MATCH:

printf(format,"EXACT",buf,ele->text,buf_dup,ele->dup,diff);
++EXACT;
break;
case CNG_ONE:

printf(format,"C1",buf,ele->text,buf_dup,ele->dup,diff);
++C1;
break;
case ADD_ONE:

printf(format,"A1",buf,ele->text,buf_dup,ele->dup,diff);
++A1;
break;
case DEL_ONE:

printf(format,"D1",buf,ele->text,buf_dup,ele->dup,diff);
++D1;
break;
case CNG_TWO:

printf(format,"C2",buf,ele->text,buf_dup,ele->dup,diff);
++C2;
break;
case ADD_TWO:

printf(format,"A2",buf,ele->text,buf_dup,ele->dup,diff);
++A2;
break;
case DEL_TWO:

printf(format,"D2",buf,ele->text,buf_dup,ele->dup,diff);
++D2;
break;
case ADD_ONE_CNG_ONE:

printf(format,"A1C1",buf,ele->text,buf_dup,ele->dup,diff);
++A1C1;
break;
case ADD_ONE_DEL_ONE:

printf(format,"A1D1",buf,ele->text,buf_dup,ele->dup,diff);
++A1D1;
break;
case DEL_ONE_CNG_ONE:

printf(format,"D1C1",buf,ele->text,buf_dup,ele->dup,diff);
++D1C1;
break;
}
diff[pos1] = diff[pos2] = ' ';
ele = ele->next;
}
if(++count % 100 == 0 ) fprintf(stderr,"%d %s\n",count,buf);
/*
if( count > 200 ) break;
*/
}
fclose(fq);
fprintf(stderr,"EXACT %d C1 %d A1 %d D1 %d C2 %d A2 %d D2 %d A1D1 %d
A1C1 %d D1C1 %d\n",
EXACT,C1,A1,D1,C2,A2,D2,A1D1,A1C1,D1C1);
}

Attachment: cspellin.pl
Description: Perl program




Archive powered by MHonArc 2.6.24.

Top of Page