Помехоустойчивый поиск

В рассмотренных методах поиска негласно предполагалось, что ключи однозначно закреплены за соответствующими записями и не содержат ошибок. Между тем очень сложно добиться того, чтобы в больших базах данных соблюдалась абсолютная точность записи значений полей всех видов. Участие человека-оператора в процедурах ввода данных делает ошибки неизбежными. Например, принято считать, что частота ошибок при вводе с клавиатуры достигает порой 1% и далеко не всегда их удается обнаружить и исправить.

Неточность данных может быть обусловлена и другими причинами. В частности, ключевое слово может быть известно только по звучанию, а некоторые собственные имена даже теоретически допускают неоднозначное написание. Следовательно, большое значение имеет построение алгоритмов, способных осуществлять поиск в условиях помех.

Например, предположим, что в роли ключей выступают слова, которые могли быть слегка искажены, и мы хотели бы найти нужную запись, несмотря на эту ошибку. Если сделать две копии файла, в одной из которых ключи расположены в обычном алфавитном порядке, а в другой они упорядочены справа налево (как если бы слова были прочитаны наоборот), искаженный аргумент поиска в большинстве случаев совпадает до половины своей длины или более с записью одного из этих двух файлов. Таким способом удается отыскать возможные претенденты на искомую запись.

Другая идея решения этой задачи состоит в том, чтобы найти некоторое преобразование аргумента в код (маску), собирающий вместе все варианты данного ключа. За рубежом нашел широкое применение следующий метод кодирования фамилий:

а) оставить первую букву; все буквы A, E, H, I, O, U, W, Y, стоящие на других местах, - вычеркнуть;

б) оставшимся буквам (кроме первой) присвоить следующие значения:

(B, F, P, V) -> 1;

(C, G, J, K, Q, S, X, Z) -> 2;

(D, T) -> 3;

L -> 4;

(M, N) -> 5;

R -> 6;

в) если в исходном имени (перед шагом а) рядом стояли несколько букв с одинаковыми кодами, пренебречь всеми, кроме первой из этой группы;

г) дописывая в случае надобности нули или опуская лишние цифры, преобразовать полученное выражение в форму «одна буква, три цифры».

Например:

Разумеется, такая система собирает вместе не только родственные, но и достаточно различные имена. С другой стороны, некоторые родственные имена могут иметь различную кодировку. Но, вообще говоря, этот метод намного увеличивает вероятность обнаружить имя под одной из его масок.