double_metaphone.c

Revision 1736, 28.4 kB (checked in by karman, 4 years ago)
changed license header to refer to COPYING for exception details
Property svn:eol-style set to `native` Property svn:executable set to ``* Property svn:keywords set to `Author Date Id Revision`

Line
1	/*
2	$Id$
3	**
4
5	This file is part of Swish-e.
6
7	Swish-e is free software; you can redistribute it and/or modify
8	it under the terms of the GNU General Public License as published by
9	the Free Software Foundation; either version 2 of the License, or
10	(at your option) any later version.
11
12	Swish-e is distributed in the hope that it will be useful,
13	but WITHOUT ANY WARRANTY; without even the implied warranty of
14	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15	GNU General Public License for more details.
16
17	You should have received a copy of the GNU General Public License
18	along with Swish-e; if not, write to the Free Software
19	Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20
21	See the COPYING file that accompanies the Swish-e distribution for details
22	of the GNU GPL and the special exception available for linking against
23	the Swish-e library.
24
25	** Mon May 9 15:51:39 CDT 2005
26	** added GPL
27
28
29	**
30	** August 20, 2002 moseley - first added to swish-e
31	**
32	** this is a very slightly modified version of the double_metaphone.c code
33	** from the Perl module Text::DoubleMetaphone by Maurice Aubrey, and based
34	** on the work of Lawrence Philips.
35	** See http://aspell.sourceforge.net/metaphone
36	**
37	** From the Text::DoubleMetaphone README file:
38
39	DESCRIPTION
40
41	This module implements a "sounds like" algorithm developed
42	by Lawrence Philips which he published in the June, 2000 issue
43	of C/C++ Users Journal. Double Metaphone is an improved
44	version of Philips' original Metaphone algorithm.
45
46	COPYRIGHT
47
48	Copyright 2000, Maurice Aubrey <maurice@hevanet.com>.
49	All rights reserved.
50
51	This code is based heavily on the C++ implementation by
52	Lawrence Philips and incorporates several bug fixes courtesy
53	of Kevin Atkinson <kevina@users.sourceforge.net>.
54
55	This module is free software; you may redistribute it and/or
56	modify it under the same terms as Perl itself.
57
58
59	** Mon May 9 16:19:47 CDT 2005
60	** "the same terms as Perl itself" means GPL if we want it. We do.
61	**
62
63	**
64	**
65	*/
66
67
68
69	#include <stdio.h>
70	#include <ctype.h>
71	#include <stdlib.h>
72	#include <string.h>
73	#include <stdarg.h>
74	#include <assert.h>
75	#include "swish.h" // $$$ yikes, sure brings in a lot
76	#include "double_metaphone.h"
77	#include "mem.h"
78
79
80	#define META_MALLOC(v,n,t) (v = (t)emalloc(((n)sizeof(t))))
81
82	#define META_REALLOC(v,n,t) (v = (t)erealloc((v),((n)sizeof(t))))
83
84	#define META_FREE(x) efree((x))
85
86
87	metastring *
88	NewMetaString(char *init_str)
89	{
90	metastring *s;
91	char empty_string[] = "";
92
93	META_MALLOC(s, 1, metastring);
94	assert( s != NULL );
95
96	if (init_str == NULL)
97	init_str = empty_string;
98	s->length = strlen(init_str);
99	/ preallocate a bit more for potential growth /
100	s->bufsize = s->length + 7;
101
102	META_MALLOC(s->str, s->bufsize, char);
103	assert( s->str != NULL );
104
105	strncpy(s->str, init_str, s->length + 1);
106	s->free_string_on_destroy = 1;
107
108	return s;
109	}
110
111
112	void
113	DestroyMetaString(metastring * s)
114	{
115	if (s == NULL)
116	return;
117
118	if (s->free_string_on_destroy && (s->str != NULL))
119	META_FREE(s->str);
120
121	META_FREE(s);
122	}
123
124
125	void
126	IncreaseBuffer(metastring * s, int chars_needed)
127	{
128	META_REALLOC(s->str, (s->bufsize + chars_needed + 10), char);
129	assert( s->str != NULL );
130	s->bufsize = s->bufsize + chars_needed + 10;
131	}
132
133
134	void
135	MakeUpper(metastring * s)
136	{
137	char *i;
138
139	for (i = s->str; *i; i++)
140	{
141	i = toupper(i);
142	}
143	}
144
145
146	int
147	IsVowel(metastring * s, int pos)
148	{
149	char c;
150
151	if ((pos < 0) \|\| (pos >= s->length))
152	return 0;
153
154	c = *(s->str + pos);
155	if ((c == 'A') \|\| (c == 'E') \|\| (c == 'I') \|\| (c =='O') \|\|
156	(c =='U') \|\| (c == 'Y'))
157	return 1;
158
159	return 0;
160	}
161
162
163	int
164	SlavoGermanic(metastring * s)
165	{
166	if ((char ) strstr(s->str, "W"*))
167	return 1;
168	else if ((char ) strstr(s->str, "K"*))
169	return 1;
170	else if ((char ) strstr(s->str, "CZ"*))
171	return 1;
172	else if ((char ) strstr(s->str, "WITZ"*))
173	return 1;
174	else
175	return 0;
176	}
177
178
179	int
180	GetLength(metastring * s)
181	{
182	return s->length;
183	}
184
185
186	char
187	GetAt(metastring * s, int pos)
188	{
189	if ((pos < 0) \|\| (pos >= s->length))
190	return '\0';
191
192	return ((char) *(s->str + pos));
193	}
194
195
196	void
197	SetAt(metastring * s, int pos, char c)
198	{
199	if ((pos < 0) \|\| (pos >= s->length))
200	return;
201
202	*(s->str + pos) = c;
203	}
204
205
206	/*
207	Caveats: the START value is 0 based
208	*/
209	int
210	StringAt(metastring * s, int start, int length, ...)
211	{
212	char *test;
213	char *pos;
214	va_list ap;
215
216	if ((start < 0) \|\| (start >= s->length))
217	return 0;
218
219	pos = (s->str + start);
220	va_start(ap, length);
221
222	do
223	{
224	test = va_arg(ap, char *);
225	if (*test && (strncmp(pos, test, length) == 0))
226	return 1;
227	}
228	while (strcmp(test, ""));
229
230	va_end(ap);
231
232	return 0;
233	}
234
235
236	void
237	MetaphAdd(metastring * s, char *new_str)
238	{
239	int add_length;
240
241	if (new_str == NULL)
242	return;
243
244	add_length = strlen(new_str);
245	if ((s->length + add_length) > (s->bufsize - 1))
246	{
247	IncreaseBuffer(s, add_length);
248	}
249
250	strcat(s->str, new_str);
251	s->length += add_length;
252	}
253
254
255	void
256	DoubleMetaphone(const char str, char* **codes)
257	{
258	int length;
259	metastring *original;
260	metastring *primary;
261	metastring *secondary;
262	int current;
263	int last;
264
265	current = 0;
266	/ we need the real length and last prior to padding /
267	length = strlen(str);
268	last = length - 1;
269	original = NewMetaString((char *)str);
270	/ Pad original so we can index beyond end /
271	MetaphAdd(original, " ");
272
273	primary = NewMetaString("");
274	secondary = NewMetaString("");
275	primary->free_string_on_destroy = 0;
276	secondary->free_string_on_destroy = 0;
277
278	MakeUpper(original);
279
280	/ skip these when at start of word /
281	if (StringAt(original, 0, 2, "GN", "KN", "PN", "WR", "PS", ""))
282	current += 1;
283
284	/ Initial 'X' is pronounced 'Z' e.g. 'Xavier' /
285	if (GetAt(original, 0) == 'X')
286	{
287	MetaphAdd(primary, "S"); / 'Z' maps to 'S' /
288	MetaphAdd(secondary, "S");
289	current += 1;
290	}
291
292	/ main loop /
293	while ((primary->length < 4) \|\| (secondary->length < 4))
294	{
295	if (current >= length)
296	break;
297
298	switch (GetAt(original, current))
299	{
300	case 'A':
301	case 'E':
302	case 'I':
303	case 'O':
304	case 'U':
305	case 'Y':
306	if (current == 0)
307	{
308	/ all init vowels now map to 'A' /
309	MetaphAdd(primary, "A");
310	MetaphAdd(secondary, "A");
311	}
312	current += 1;
313	break;
314
315	case 'B':
316
317	/ "-mb", e.g", "dumb", already skipped over... /
318	MetaphAdd(primary, "P");
319	MetaphAdd(secondary, "P");
320
321	if (GetAt(original, current + 1) == 'B')
322	current += 2;
323	else
324	current += 1;
325	break;
326
327	case 'Ç':
328	MetaphAdd(primary, "S");
329	MetaphAdd(secondary, "S");
330	current += 1;
331	break;
332
333	case 'C':
334	/ various germanic /
335	if ((current > 1)
336	&& !IsVowel(original, current - 2)
337	&& StringAt(original, (current - 1), 3, "ACH", "")
338	&& ((GetAt(original, current + 2) != 'I')
339	&& ((GetAt(original, current + 2) != 'E')
340	\|\| StringAt(original, (current - 2), 6, "BACHER",
341	"MACHER", ""))))
342	{
343	MetaphAdd(primary, "K");
344	MetaphAdd(secondary, "K");
345	current += 2;
346	break;
347	}
348
349	/ special case 'caesar' /
350	if ((current == 0)
351	&& StringAt(original, current, 6, "CAESAR", ""))
352	{
353	MetaphAdd(primary, "S");
354	MetaphAdd(secondary, "S");
355	current += 2;
356	break;
357	}
358
359	/ italian 'chianti' /
360	if (StringAt(original, current, 4, "CHIA", ""))
361	{
362	MetaphAdd(primary, "K");
363	MetaphAdd(secondary, "K");
364	current += 2;
365	break;
366	}
367
368	if (StringAt(original, current, 2, "CH", ""))
369	{
370	/ find 'michael' /
371	if ((current > 0)
372	&& StringAt(original, current, 4, "CHAE", ""))
373	{
374	MetaphAdd(primary, "K");
375	MetaphAdd(secondary, "X");
376	current += 2;
377	break;
378	}
379
380	/ greek roots e.g. 'chemistry', 'chorus' /
381	if ((current == 0)
382	&& (StringAt(original, (current + 1), 5, "HARAC", "HARIS", "")
383	\|\| StringAt(original, (current + 1), 3, "HOR",
384	"HYM", "HIA", "HEM", ""))
385	&& !StringAt(original, 0, 5, "CHORE", ""))
386	{
387	MetaphAdd(primary, "K");
388	MetaphAdd(secondary, "K");
389	current += 2;
390	break;
391	}
392
393	/ germanic, greek, or otherwise 'ch' for 'kh' sound /
394	if (
395	(StringAt(original, 0, 4, "VAN ", "VON ", "")
396	\|\| StringAt(original, 0, 3, "SCH", ""))
397	/ 'architect but not 'arch', 'orchestra', 'orchid' /
398	\|\| StringAt(original, (current - 2), 6, "ORCHES",
399	"ARCHIT", "ORCHID", "")
400	\|\| StringAt(original, (current + 2), 1, "T", "S",
401	"")
402	\|\| ((StringAt(original, (current - 1), 1, "A", "O", "U", "E", "")
403	\|\| (current == 0))
404	/ e.g., 'wachtler', 'wechsler', but not 'tichner' /
405	&& StringAt(original, (current + 2), 1, "L", "R",
406	"N", "M", "B", "H", "F", "V", "W", " ", "")))
407	{
408	MetaphAdd(primary, "K");
409	MetaphAdd(secondary, "K");
410	}
411	else
412	{
413	if (current > 0)
414	{
415	if (StringAt(original, 0, 2, "MC", ""))
416	{
417	/ e.g., "McHugh" /
418	MetaphAdd(primary, "K");
419	MetaphAdd(secondary, "K");
420	}
421	else
422	{
423	MetaphAdd(primary, "X");
424	MetaphAdd(secondary, "K");
425	}
426	}
427	else
428	{
429	MetaphAdd(primary, "X");
430	MetaphAdd(secondary, "X");
431	}
432	}
433	current += 2;
434	break;
435	}
436	/ e.g, 'czerny' /
437	if (StringAt(original, current, 2, "CZ", "")
438	&& !StringAt(original, (current - 2), 4, "WICZ", ""))
439	{
440	MetaphAdd(primary, "S");
441	MetaphAdd(secondary, "X");
442	current += 2;
443	break;
444	}
445
446	/ e.g., 'focaccia' /
447	if (StringAt(original, (current + 1), 3, "CIA", ""))
448	{
449	MetaphAdd(primary, "X");
450	MetaphAdd(secondary, "X");
451	current += 3;
452	break;
453	}
454
455	/ double 'C', but not if e.g. 'McClellan' /
456	if (StringAt(original, current, 2, "CC", "")
457	&& !((current == 1) && (GetAt(original, 0) == 'M')))
458	{
459	/ 'bellocchio' but not 'bacchus' /
460	if (StringAt(original, (current + 2), 1, "I", "E", "H", "")
461	&& !StringAt(original, (current + 2), 2, "HU", ""))
462	{
463	/ 'accident', 'accede' 'succeed' /
464	if (
465	((current == 1)
466	&& (GetAt(original, current - 1) == 'A'))
467	\|\| StringAt(original, (current - 1), 5, "UCCEE",
468	"UCCES", ""))
469	{
470	MetaphAdd(primary, "KS");
471	MetaphAdd(secondary, "KS");
472	/ 'bacci', 'bertucci', other italian /
473	}
474	else
475	{
476	MetaphAdd(primary, "X");
477	MetaphAdd(secondary, "X");
478	}
479	current += 3;
480	break;
481	}
482	else
483	{ / Pierce's rule /
484	MetaphAdd(primary, "K");
485	MetaphAdd(secondary, "K");
486	current += 2;
487	break;
488	}
489	}
490
491	if (StringAt(original, current, 2, "CK", "CG", "CQ", ""))
492	{
493	MetaphAdd(primary, "K");
494	MetaphAdd(secondary, "K");
495	current += 2;
496	break;
497	}
498
499	if (StringAt(original, current, 2, "CI", "CE", "CY", ""))
500	{
501	/ italian vs. english /
502	if (StringAt
503	(original, current, 3, "CIO", "CIE", "CIA", ""))
504	{
505	MetaphAdd(primary, "S");
506	MetaphAdd(secondary, "X");
507	}
508	else
509	{
510	MetaphAdd(primary, "S");
511	MetaphAdd(secondary, "S");
512	}
513	current += 2;
514	break;
515	}
516
517	/ else /
518	MetaphAdd(primary, "K");
519	MetaphAdd(secondary, "K");
520
521	/ name sent in 'mac caffrey', 'mac gregor /
522	if (StringAt(original, (current + 1), 2, " C", " Q", " G", ""))
523	current += 3;
524	else
525	if (StringAt(original, (current + 1), 1, "C", "K", "Q", "")
526	&& !StringAt(original, (current + 1), 2, "CE", "CI", ""))
527	current += 2;
528	else
529	current += 1;
530	break;
531
532	case 'D':
533	if (StringAt(original, current, 2, "DG", ""))
534	{
535	if (StringAt(original, (current + 2), 1, "I", "E", "Y", ""))
536	{
537	/ e.g. 'edge' /
538	MetaphAdd(primary, "J");
539	MetaphAdd(secondary, "J");
540	current += 3;
541	break;
542	}
543	else
544	{
545	/ e.g. 'edgar' /
546	MetaphAdd(primary, "TK");
547	MetaphAdd(secondary, "TK");
548	current += 2;
549	break;
550	}
551	}
552
553	if (StringAt(original, current, 2, "DT", "DD", ""))
554	{
555	MetaphAdd(primary, "T");
556	MetaphAdd(secondary, "T");
557	current += 2;
558	break;
559	}
560
561	/ else /
562	MetaphAdd(primary, "T");
563	MetaphAdd(secondary, "T");
564	current += 1;
565	break;
566
567	case 'F':
568	if (GetAt(original, current + 1) == 'F')
569	current += 2;
570	else
571	current += 1;
572	MetaphAdd(primary, "F");
573	MetaphAdd(secondary, "F");
574	break;
575
576	case 'G':
577	if (GetAt(original, current + 1) == 'H')
578	{
579	if ((current > 0) && !IsVowel(original, current - 1))
580	{
581	MetaphAdd(primary, "K");
582	MetaphAdd(secondary, "K");
583	current += 2;
584	break;
585	}
586
587	if (current < 3)
588	{
589	/ 'ghislane', ghiradelli /
590	if (current == 0)
591	{
592	if (GetAt(original, current + 2) == 'I')
593	{
594	MetaphAdd(primary, "J");
595	MetaphAdd(secondary, "J");
596	}
597	else
598	{
599	MetaphAdd(primary, "K");
600	MetaphAdd(secondary, "K");
601	}
602	current += 2;
603	break;
604	}
605	}
606	/ Parker's rule (with some further refinements) - e.g., 'hugh' /
607	if (
608	((current > 1)
609	&& StringAt(original, (current - 2), 1, "B", "H", "D", ""))
610	/ e.g., 'bough' /
611	\|\| ((current > 2)
612	&& StringAt(original, (current - 3), 1, "B", "H", "D", ""))
613	/ e.g., 'broughton' /
614	\|\| ((current > 3)
615	&& StringAt(original, (current - 4), 1, "B", "H", "")))
616	{
617	current += 2;
618	break;
619	}
620	else
621	{
622	/ e.g., 'laugh', 'McLaughlin', 'cough', 'gough', 'rough', 'tough' /
623	if ((current > 2)
624	&& (GetAt(original, current - 1) == 'U')
625	&& StringAt(original, (current - 3), 1, "C",
626	"G", "L", "R", "T", ""))
627	{
628	MetaphAdd(primary, "F");
629	MetaphAdd(secondary, "F");
630	}
631	else if ((current > 0)
632	&& GetAt(original, current - 1) != 'I')
633	{
634
635
636	MetaphAdd(primary, "K");
637	MetaphAdd(secondary, "K");
638	}
639
640	current += 2;
641	break;
642	}
643	}
644
645	if (GetAt(original, current + 1) == 'N')
646	{
647	if ((current == 1) && IsVowel(original, 0)
648	&& !SlavoGermanic(original))
649	{
650	MetaphAdd(primary, "KN");
651	MetaphAdd(secondary, "N");
652	}
653	else
654	/ not e.g. 'cagney' /
655	if (!StringAt(original, (current + 2), 2, "EY", "")
656	&& (GetAt(original, current + 1) != 'Y')
657	&& !SlavoGermanic(original))
658	{
659	MetaphAdd(primary, "N");
660	MetaphAdd(secondary, "KN");
661	}
662	else
663	{
664	MetaphAdd(primary, "KN");
665	MetaphAdd(secondary, "KN");
666	}
667	current += 2;
668	break;
669	}
670
671	/ 'tagliaro' /
672	if (StringAt(original, (current + 1), 2, "LI", "")
673	&& !SlavoGermanic(original))
674	{
675	MetaphAdd(primary, "KL");
676	MetaphAdd(secondary, "L");
677	current += 2;
678	break;
679	}
680
681	/ -ges-,-gep-,-gel-, -gie- at beginning /
682	if ((current == 0)
683	&& ((GetAt(original, current + 1) == 'Y')
684	\|\| StringAt(original, (current + 1), 2, "ES", "EP",
685	"EB", "EL", "EY", "IB", "IL", "IN", "IE",
686	"EI", "ER", "")))
687	{
688	MetaphAdd(primary, "K");
689	MetaphAdd(secondary, "J");
690	current += 2;
691	break;
692	}
693
694	/ -ger-, -gy- /
695	if (
696	(StringAt(original, (current + 1), 2, "ER", "")
697	\|\| (GetAt(original, current + 1) == 'Y'))
698	&& !StringAt(original, 0, 6, "DANGER", "RANGER", "MANGER", "")
699	&& !StringAt(original, (current - 1), 1, "E", "I", "")
700	&& !StringAt(original, (current - 1), 3, "RGY", "OGY",
701	""))
702	{
703	MetaphAdd(primary, "K");
704	MetaphAdd(secondary, "J");
705	current += 2;
706	break;
707	}
708
709	/ italian e.g, 'biaggi' /
710	if (StringAt(original, (current + 1), 1, "E", "I", "Y", "")
711	\|\| StringAt(original, (current - 1), 4, "AGGI", "OGGI", ""))
712	{
713	/ obvious germanic /
714	if (
715	(StringAt(original, 0, 4, "VAN ", "VON ", "")
716	\|\| StringAt(original, 0, 3, "SCH", ""))
717	\|\| StringAt(original, (current + 1), 2, "ET", ""))
718	{
719	MetaphAdd(primary, "K");
720	MetaphAdd(secondary, "K");
721	}
722	else
723	{
724	/ always soft if french ending /
725	if (StringAt
726	(original, (current + 1), 4, "IER ", ""))
727	{
728	MetaphAdd(primary, "J");
729	MetaphAdd(secondary, "J");
730	}
731	else
732	{
733	MetaphAdd(primary, "J");
734	MetaphAdd(secondary, "K");
735	}
736	}
737	current += 2;
738	break;
739	}
740
741	if (GetAt(original, current + 1) == 'G')
742	current += 2;
743	else
744	current += 1;
745	MetaphAdd(primary, "K");
746	MetaphAdd(secondary, "K");
747	break;
748
749	case 'H':
750	/ only keep if first & before vowel or btw. 2 vowels /
751	if (((current == 0) \|\| IsVowel(original, current - 1))
752	&& IsVowel(original, current + 1))
753