Помехоустойчивый поиск
В рассмотренных методах поиска негласно предполагалось, что ключи однозначно закреплены за соответствующими записями и не содержат ошибок. Между тем очень сложно добиться того, чтобы в больших базах данных соблюдалась абсолютная точность записи значений полей всех видов. Участие человека-оператора в процедурах ввода данных делает ошибки неизбежными. Например, принято считать, что частота ошибок при вводе с клавиатуры достигает порой 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;
в) если в исходном имени (перед шагом а) рядом стояли несколько букв с одинаковыми кодами, пренебречь всеми, кроме первой из этой группы;
г) дописывая в случае надобности нули или опуская лишние цифры, преобразовать полученное выражение в форму «одна буква, три цифры».
Например:
Ключевое слово | Код маски |
EULER | E460 |
GAUSS | G200 |
HILBERT | H416 |
KNUTH | K530 |
Разумеется, такая система собирает вместе не только родственные, но и достаточно различные имена. С другой стороны, некоторые родственные имена могут иметь различную кодировку. Но, вообще говоря, этот метод намного увеличивает вероятность обнаружить имя под одной из его масок.
Дата добавления: 2017-11-04; просмотров: 408;