soundEx algorithm

Немного о фонетических алгоритмах

Фонетические алгоритмы — алгоритмы, которые сопоставляют двум словам со схожим произношением одинаковые коды, что позволяет осуществлять сравнение и индексацию множества таких слов на основе их фонетического сходства. Существует достаточно много фонетических алгоритмов, например: NYSIIS, Metaphone, Double Metaphone, Caverphone и т.д. В данном отчёте я напишу об одном из фонетических алгоритмов, который называется soundEx.
soundEx — алгоритм, который был разработан Робертом Расселом и Маргарет Кинг Оделл в 10-х годах прошлого века. В основном, этот алгоритм стал известен после того, как был опубликован в книге Дональда Кнута «Искусство программирования».

soundEx

Пример:

Код	Слово
a500	ammonium
i514	implementation

Данным алгоритмом предусмотрено сопоставление индекса вида LNNN(Q123) слову. Этот код получают следуя следующему алгоритму:

Первая буква сохраняется
Все гласные звуки + буквы h, w отбрасываются
Оставшиеся буквы заменяются цифрами в диапазоне от 1 до 6 по следующим правилам:

B, P, F, V 1

C, S, K, G, J, Q, X, Z 2

D, T 3

L 4

M, N 5

R 6
Последовательность из одинаковых цифр заменяется одной такой цифрой
Полученная строка обрезается до первых 4-х символов. Если в строке меньше 4х, то в конец добавляются нули.

Пример:

javalanguage → jvlngg → j214522 → j21452 → j214

Реализация:

Реализация soundEx приводится по выше описанному алгоритму.
Для тестирования создадим HashMap, в котором по ключу-индексу soundEx будем создавать список слов, подходящих под этот ключ.

import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef {
	public static String soundEx (String a){
		int n = a.length();
		char [] sdx = a.toUpperCase().toCharArray();
		char fl = sdx[0];
		for (int i = 0 ; i < n; i++){
			switch(sdx[i]) {
				case 'B' :
				case 'P' :
				case 'F' :
				case 'V' :
					sdx[i] = '1';
					break;
				case 'C':
				case 'S':
				case 'K':
				case 'G':
				case 'J':
				case 'Q':
				case 'X':
				case 'Z':
					sdx[i] = '2';
					break;
				case 'D':
				case 'T':
					sdx[i] = '3';
					break;
				case 'L':
					sdx[i] = '4';
					break;
				case 'M':
				case 'N':
					sdx[i] = '5';
					break;
				case 'R' :
					sdx[i] = '6';
					break;
				default: 
					sdx[i] = '0';
					break;
			}
		}
		String retSdx = "" + fl;
		for (int i = 0; i < sdx.length; i++){
			if (sdx[i] != '0') {
				retSdx += sdx[i];
			}
		}
		String ans = ""+fl;
		for (int i = 1; i < retSdx.length(); i++){
			if (retSdx.charAt(i) != (retSdx.charAt(i-1))) {
				ans += retSdx.charAt(i);
			}
		}
		ans = ans + "0000";
		return ans.substring(0, 4);
	}
	public static void main (String[] args) {
		Map <String, List<String> > words = new HashMap<String, List<String> > ();
		Scanner in = new Scanner (System.in);
		String input = in.nextLine();
		input = " " + input;
		String [] t = input.split(" ");
		for (int i = 1; i < t.length; i++) {
			List<String> L = words.get(soundEx(t[i]));
	    	if (L == null)
				words.put(soundEx(t[i]), L=new ArrayList<String>());
			L.add(t[i]);
		}
		for (Object x : words.keySet()){
			System.out.print(x + ": ");
			List<String> L = words.get(x);
			for (Object y : L) System.out.print(y + " ");
			System.out.println();
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Codechef {

public static String soundEx (String a){

int n = a.length();

char [] sdx = a.toUpperCase().toCharArray();

char fl = sdx[0];

for (int i = 0 ; i < n; i++){

switch(sdx[i]) {

case 'B' :

case 'P' :

case 'F' :

case 'V' :

sdx[i] = '1';

break;

case 'C':

case 'S':

case 'K':

case 'G':

case 'J':

case 'Q':

case 'X':

case 'Z':

sdx[i] = '2';

break;

case 'D':

case 'T':

sdx[i] = '3';

break;

case 'L':

sdx[i] = '4';

break;

case 'M':

case 'N':

sdx[i] = '5';

break;

case 'R' :

sdx[i] = '6';

break;

default:

sdx[i] = '0';

break;

}

String retSdx = "" + fl;

for (int i = 0; i < sdx.length; i++){

if (sdx[i] != '0') {

retSdx += sdx[i];

}

String ans = ""+fl;

for (int i = 1; i < retSdx.length(); i++){

if (retSdx.charAt(i) != (retSdx.charAt(i-1))) {

ans += retSdx.charAt(i);

}

ans = ans + "0000";

return ans.substring(0, 4);

}

public static void main (String[] args) {

Map <String, List<String> > words = new HashMap<String, List<String> > ();

Scanner in = new Scanner (System.in);

String input = in.nextLine();

input = " " + input;

String [] t = input.split(" ");

for (int i = 1; i < t.length; i++) {

List<String> L = words.get(soundEx(t[i]));

if (L == null)

words.put(soundEx(t[i]), L=new ArrayList<String>());

L.add(t[i]);

}

for (Object x : words.keySet()){

System.out.print(x + ": ");

List<String> L = words.get(x);

for (Object y : L) System.out.print(y + " ");

System.out.println();

}

Ссылка на Ideone

Пример:

In: Dedlovskiy Dedlovskih Nasimov Nagimov Zazimov Azazimov Marchenko Merchenko Dedlovich Nagiev Houston Watson
Out:
N521: Nagiev
D341: Dedlovskiy Dedlovskih Dedlovich
A251: Azazimov
M562: Marchenko Merchenko
W325: Watson
Z251: Zazimov
H235: Houston
N525: Nasimov Nagimov

Facebook
X
Shares

2 thoughts on “soundEx algorithm”

Александр Антоненко says: 26/12/2015 at 09:36

Засчитано, 20 баллов.

Ответить
Денис Кондрашов says: 05/05/2019 at 10:09

В примере неправильный код выведен. Первая J в javalanguage просто остается первой, и не учитывается при переводе в цифры. J214 — это не верный код. Правильнее будет J145. Если код реализации составлен так, что считает первую букву тоже, то он требует коррекции

Ответить

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

soundEx algorithm

Немного о фонетических алгоритмах

soundEx

Пример:

Реализация:

Пример:

2 thoughts on “soundEx algorithm”

Добавить комментарий Отменить ответ