Реализации алгоритмов/Редакционное предписание

Алгоритмы по поиску редакционного предписания. Написаны на языке Java.

Используются следующий класс для хранения предписания:

class Prescription {
	public String route;
	public int distance;
	Prescription(int distance, String route) {
		this.distance = distance;
		this.route = route;
	}
}

С максимальной скоростью

$\Theta (n^{2})$ времени и $\Theta (n^{2})$ памяти

Prescription Levenshtein1(String S1, String S2) {
	int m = S1.length(), n = S2.length();
	int[][] D = new int[m + 1][n + 1];
	char[][] P = new char[m + 1][n + 1];

	// Базовые значения
	for (int i = 0; i <= m; i++) {
		D[i][0] = i;
		P[i][0] = 'D';
	}
	for (int i = 0; i <= n; i++) {
		D[0][i] = i;
		P[0][i] = 'I';
	}

	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++) {
			int cost = (S1.charAt(i - 1) != S2.charAt(j - 1)) ? 1 : 0;
			if(D[i][j - 1] < D[i - 1][j] && D[i][j - 1] < D[i - 1][j - 1] + cost) {
				//Вставка
				D[i][j] = D[i][j - 1] + 1;
				P[i][j] = 'I';
			}
			else if(D[i - 1][j] < D[i - 1][j - 1] + cost) {
				//Удаление
				D[i][j] = D[i - 1][j] + 1;
				P[i][j] = 'D';
			}
			else {
				//Замена или отсутствие операции
				D[i][j] = D[i - 1][j - 1] + cost;
				P[i][j] = (cost == 1) ? 'R' : 'M';
			}
		}

	//Восстановление предписания
	StringBuilder route = new StringBuilder("");
	int i = m, j = n;
	do {
		char c = P[i][j];
		route.append(c);
		if(c == 'R' || c == 'M') {
			i --;
			j --;
		}
		else if(c == 'D') {
			i --;
		}
		else {
			j --;
		}
	} while((i != 0) || (j != 0));
	return new Prescription(D[m][n], route.reverse().toString());
}

С минимальным потреблением памяти

• $\Theta (n^{3})$ времени и $\Theta (n)$ памяти

Prescription Levenshtein2(String S1, String S2) {
	int m = S1.length(), n = S2.length();
	int[] D1 = new int[n + 1];
	int[] D2 = new int[n + 1];
	char[] P1 = new char[n + 1];
	char[] P2 = new char[n + 1];

	int d = 0;
	StringBuilder route = new StringBuilder("");
	int iPos = m, jPos = n;
	do {
		for(int i = 0; i <= jPos; i ++)
			D2[i] = i;

		for(int i = 1; i <= iPos; i ++) {

			D1 = D2;
			D2 = new int[jPos + 1];

			P1 = P2;
			P2 = new char[jPos + 1];

			for(int j = 0; j <= jPos; j ++) {
				if(j == 0) D2[j] = i;
				else {
					int cost = (S1.charAt(i - 1) != S2.charAt(j - 1)) ? 1 : 0;
					if(D2[j - 1] < D1[j] && D2[j - 1] < D1[j - 1] + cost) {
						//Вставка
						D2[j] = D2[j - 1] + 1;
						P2[j] = 'I';
					}
					else if(D1[j] < D1[j - 1] + cost) {
						//Удаление
						D2[j] = D1[j] + 1;
						P2[j] = 'D';
					}
					else {
						//Замена или отсутствие операции
						D2[j] = D1[j - 1] + cost;
						P2[j] = (cost == 1) ? 'R' : 'M';
					}
				}
			}
		}
		if(iPos == m && jPos == n) d = D2[n];
		//Восстановление действий за две последние строки
		int _iPos = iPos;
		while(iPos >= _iPos - 1 && iPos !=0 && jPos != 0) {
			char c = (iPos == _iPos) ? P2[jPos] : P1[jPos];
			route.append(c);
			if(c == 'R' || c == 'M') {
				iPos --;
				jPos --;
			}
			else if(c == 'D') {
				iPos --;
			}
			else {
				jPos --;
			}
		}
	} while((iPos != 0) && (jPos != 0));
	return new Prescription(d, route.reverse().toString());
}

Сбалансированный вариант

• $\Theta (n^{2}\cdot {\sqrt {n}})$ времени и $\Theta (n\cdot {\sqrt {n}})$ памяти

Prescription Levenshtein3(String S1, String S2) {
	int m = S1.length(), n = S2.length();
	int h = (int)Math.sqrt(m + 1);
	int[][] D = new int[h + 1][n + 1];
	char[][] P = new char[h + 1][n + 1];

	int d = 0;
	StringBuilder route = new StringBuilder("");
	int iPos = m, jPos = n;
	do {
		for (int i = 0; i <= jPos; i++) {
			D[0][i] = i;
			P[0][i] = 'I';
		}
		int _i = 1;
		for(int i = 1; i <= iPos; i ++) {
			for(int j = 0; j <= jPos; j ++) {
				if(j == 0) D[_i][j] = i;
				else {
					int cost = (S1.charAt(i - 1) != S2.charAt(j - 1)) ? 1 : 0;
					if(D[_i][j - 1] < D[_i - 1][j] && D[_i][j - 1] < D[_i - 1][j - 1] + cost) {
						//Вставка
						D[_i][j] = D[_i][j - 1] + 1;
						P[_i][j] = 'I';
					}
					else if(D[_i - 1][j] < D[_i - 1][j - 1] + cost) {
						//Удаление
						D[_i][j] = D[_i - 1][j] + 1;
						P[_i][j] = 'D';
					}
					else {
						//Замена или отсутствие операции
						D[_i][j] = D[_i - 1][j - 1] + cost;
						P[_i][j] = (cost == 1) ? 'R' : 'M';
					}
				}
			}
			if(i % h == 0) {
				//Выделение памяти для новых строк и копирование последней из прошлой полосы в первую строку новой
				int[] vRow = new int[n + 1];
				char[] cRow = new char[n + 1];
				for(int j = 0; j <= n; j ++) {
					vRow[j] = D[_i][j];
					cRow[j] = P[_i][j];
				}
				D = new int[h + 1][n + 1];
				P = new char[h + 1][n + 1];
				for(int j = 0; j <= n; j ++) {
					D[0][j] = vRow[j];
					P[0][j] = cRow[j];
				}
				_i = 0;
			}
			_i++;
		}
		if(iPos == m && jPos == n) d = D[_i - 1][n];
		//Восстановление предписания в последних _i - 1 строках
		while(_i > 0 && iPos !=0 && jPos != 0) {
			char c = P[_i - 1][jPos];
			route.append(c);
			if(c == 'R' || c == 'M') {
				iPos --;
				jPos --;
				_i --;
			}
			else if(c == 'D') {
				iPos --;
				_i --;
			}
			else {
				jPos --;
			}
		}
	} while((iPos != 0) && (jPos != 0));

	return new Prescription(d, route.reverse().toString());
}

См. также

• Реализации алгоритмов/Расстояние Левенштейна