Исследование фонетических алгоритмов
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
обным задачам относят поиск, сопоставление и слияние персональных данных о физических лицах. Это могут быть, например, списки клиентов телефонных компаний, покупателей различных товаров и услуг, клиентов банка.
Следует отметить, что изначально ни один из алгоритмов изначально не разрабатывался для сравнения данных о физических лицах. Специфика обработки имен физических лиц более полно учтена в известных алгоритмах сравнения двух строк по их звучанию - Soundex и MetaPhone. Описание алгоритма Soundex дано в классическом учебнике по программированию [1], алгоритм MetaPhone адаптирован для русского языка в работе [2]. Эти алгоритмы основаны на построении некоторой хэш-функции, преобразующей исходные строки в хэш-код, одинаковый для схожих строк. Процесс сравнения двух строк сводится к вычислению хэш-кодов этих строк и их последующего строгого сравнения. Строки, имеющие одинаковый хэш-код, считаются похожими.
Об эффективности подобных алгоритмов говорит тот факт, что в некоторых языках программирования сравнение подобного рода организовано в качестве стандартной процедуры. Например, в MySQL и PHP функция Soundex является встроенной.
Список использованных источников
1.Дональд Э. Кнут. Искусство программирования. Т. 3. Сортировка и поиск. М.: Издат. дом Вильямс, 2005.
2.Каньковски П. Как ваша фамилия, или Русский MetaPhone // Программист. 2002. №8. С. 36-39.
3.Гешвинде Э., Шениг Г. Разработка Web-приложений на PHP и PostgreSQL.
4.Лиманов Н. И., Седов М. Н. Метод автоматизированного поиска персональных данных на основе нечеткого сравнения // Информационные технологии. 2009. №11. С.
.Бойцов Л.М. Использование хеширования по сигнатуре для поиска по сходству // Прикладная математика и информатика. 2000. №7.
.Федоркова Г.О. Применение метода нечеткого поиска в операции соединения реляционных таблиц баз данных. Электронный журнал Исследовано в России, 2004.
.Международный журнал Программные продукты и системы в выпуске журнала №1 за 2011 год.
.Кнут Дональд. Искусство программирования, том 1: Пер. с англ. / Дональд Кнут. - М.: Вильямс, 2000. - 690 с.
.Марков А.А. Теория алгоритмов / А.А. Марков, Н.М. Нагорный. - М.: Наука. Главная редакция физико-математической литературы, 1984. - 432 с.
. Цыганов Н.Л. Обзор алгоритмов нечёткого сопоставления записей применительно к задаче исключения дублирования персональных данных [Электронный ресурс]/ Н.Л. Цыганов, М.В. Марковский. - Московский инженерно-физический институт, 2006. - Режим доступа:
Приложение
Программа для АЛГОРИТМА METAPHONE
#include
#include
#include
#define TRUE (1)
#define FALSE (0)
#define NULLCHAR (char *) 0*VOWELS="AEIOU",
*FRONTV="EIY",
*VARSON="CSPTG",
*DOUBLE=".";*excpPAIR="AGKPW", *nextLTR ="ENNNR";*chrptr, *chrptr1;phonetic(name,metaph,metalen)
char *name, *metaph;metalen;
{ii, jj, silent, hard, Lng, lastChr;curLtr, prevLtr, nextLtr, nextLtr2, nextLtr3;vowelAfter, vowelBefore, frontvAfter;wname[60];*ename=wname;= 0;(ii=0; name[ii] != '\0'; ii++) {(isalpha(name[ii])) {[jj] = toupper(name[ii]);++;
}
}[jj] = '\0';(strlen(ename) == 0) return;((chrptr=strchr(excpPAIR,ename[0])) != NULLCHAR)
{= nextLTR + (chrptr-excpPAIR);(*chrptr1 == ename[1]) strcpy(ename,&ename[1]);
}(ename[0] == 'X') ename[0] = 'S'; if (strncmp(ename,"WH",2) == 0) strcpy(&ename[1], &ename[2]);= strlen(ename);= Lng -1;(ename[lastChr] == 'S') {[lastChr] = '\0';= strlen(ename);= Lng -1;
}
for (ii=0; ((strlen(metaph) < metalen) && (ii < Lng)); ii++) {
curLtr = ename[ii];= FALSE; prevLtr = ' ';(ii > 0) {= ename[ii-1];(strchr(VOWELS,prevLtr) != NULLCHAR) vowelBefore = TRUE;
}(ii == 0 && (strchr(VOWELS,curLtr) != NULLCHAR)) {(metaph,&curLtr,1);;
}= FALSE; frontvAfter = FALSE; nextLtr = ' ';(ii 1 && prevLtr == 'S' && nextLtr == 'H')(metaph,"K",1);(nextLtr == 'H')(ii == 0 && (strchr(VOWELS,nextLtr2) == NULLCHAR))(metaph,"K",1);(metaph,"X",1);(prevLtr == 'C')(metaph,"C",1);(metaph,"K",1);;'D': if (nextLtr == 'G' && (strchr(FRONTV,nextLtr2) != NULLCHAR))(metaph,"J",1);(metaph,"T",1);;'G': silent=FALSE;
/* SILENT -gh- except for -gh and no vowel after h */((ii < (lastChr-1) && nextLtr == 'H')
&& (strchr(VOWELS,nextLtr2) == NULLCHAR))=TRUE;((ii == (lastChr-3))
&& nextLtr == 'N' && nextLtr2 == 'E' && nextLtr3 == 'D')=TRUE;((ii == (lastChr-1)) && nextLtr == 'N') silent=TRUE;(prevLtr == 'D' && frontvAfter) silent=TRUE;(prevLtr == 'G')=TRUE;=FALSE;(!silent)(frontvAfter && (! hard))(metaph,"J",1);(metaph,"K",1);;'H': silent = FALSE;(strchr(VARSON,prevLtr) != NULLCHAR) silent = TRUE;(vowelBefore && !vowelAfter) silent = TRUE;(!silent) strncat(metaph,&curLtr,1);;'F':'J':'L':'M':'N':'R': strncat(metaph,&curLtr,1);;'K': if (prevLtr != 'C') strncat(metaph,&curLtr,1);;'P': if (nextLtr == 'H')(metaph,"F",1);(metaph,"P",1);;'Q': strncat(metaph,"K",1);;'S': if (ii > 1 && nextLtr == 'I'
&& (nextLtr2 == 'O' || nextLtr2 == 'A'))(metaph,"X",1);(nextLtr == 'H')(metaph,"X",1);(metaph,"S",1);;'T': if (ii > 1 && nextLtr == 'I'
&& (nextLtr2 == 'O' || nextLtr2 == 'A'))(metaph,"X",1);(nextLtr == 'H')(ii > 0 || (strchr(VOWELS,nextLtr2) != NULLCHAR))(metaph,"0",1);(metaph,"T",1);(! (ii < (lastChr-2) && nextLtr == 'C' && nextLtr2 == 'H'))(metaph,"T",1);;'V': strncat(metaph,"F",1);;'W':'Y': if (ii < lastChr && vowelAfter) strncat(metaph,&curLtr,1);;'X': strncat(metaph,"KS",2);;'Z': strncat(metaph,"S",1);;;
}metaphone(argc)argc;
{name[128];metaph[50];(argc != 1) {(stderr, "metaphone: argc != 1\n");("");(1);
}(name, sizeof(name));[0] = '\0';(name,metaph,20);(metaph);(1);
}