Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Лекции ТЭИС.doc
Скачиваний:
1
Добавлен:
01.03.2025
Размер:
11 Мб
Скачать
☆

7.1.3.Фонетический поиск

Под фонетическим поиском понимается поиск по нечеткому значению ключа, если в качестве ключа используется фамилия, так как она воспринимается на слух. Наибольшее распространение при организации фонетического поиска получил метод "Soundex" [4]. Метод создает для фамилии ключ, причём похожим фамилиям или неверным написаньям одной фамилии будет соответствовать один ключ. Поэтому, если оператор городской справки, кассир в банке, авиадиспетчер или кто-либо другой наберёт вашу фамилию неверно, доступ к вашей записи в базе данных все равно будет получен, так как поиск ведётся по ключам.

Первоначально метод "Soundex" развит Маргарет К. Оуделли и Робертом К. Расселом [см.U.S.Patents 1261167 (1918), 1435663 (1922)]. Метод "Soundex" заключеется в следующем:

1.Оставить первую букву фамилии; все буквы а,е,h,i,о,u,w,у, стоящие на других местах, вычеркнуть.

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

b, f, p, v= 1;

l= 4;

c, g, j, k, q, s, x, z= 2;

m, n=5;

d, t=3;

r= 0.

3.Если в исходной фамилии рядом стояли несколько букв с одинаковыми кодами, пренебречь всеми, кроме первой из этой группы.

4.Дописывая в случае надобности нули или опуская лишние цифры, преобразовать полученное выражение в форму "буква, цифра, цифра, цифра".

Например, фамилии Euler, Gauss, Hilbert, Knuth, Lloyd и Lukasiewicz имеют коды соответственно Е460, G200, H416, K530, L300, L222.

Разумеется, такая система собирает вместе не только родственные, но и достаточно различные фамилии. Приведенные выше шесть кодов могли быть получены из фамилий Ellery, Ghosh, Heilbronn, Kant, Ladd и Lissajous. С другой стороны, такие родственные имена, как Rogers и Rodgers, Sinclair и St.Clair или Tchebysheff и Chebyshev, имеют разную кодировку. Но, вообще говоря, система "Soundex" намного увеличивает вероятность обнаружить имя под одной из его масок [4-6].

Несмотря на свою простоту, метод "Soundex" дает достаточно хорошие результаты фонетического поиска. Функции, реализующие данный метод встречаются во многих СУБД и других инструментальных средствах. Однако сам метод и большинство инструментальных средств являются англоязычными. Для фонетического поиска русских фамилий требуется модифицировать метод "Soundex" или разработать метод аналогичный по функциональным возможностям.

7.2.Алгоритмы сортировки

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

Большая часть данного раздела посвящена рассмотрению алгоритмов внутренней сортировки. В качестве объекта сортировки рассматривается массивов, т.е. сортируемые данные размещаются в оперативной памяти, организованной линейно. В разделе рассматриваются следующие алгоритмы внутренней сортировки:

  • сортировка методом пузырька;

  • сортировка вставки;

  • сортировка выбором;

  • пирамидальная сортировка;

  • быстрая сортировка.

Методы внутренней сортировки хорошо иллюстрируют как одну и ту же задачу можно решить с помощью различных алгоритмов с различной степенью эффективности.

Из методов внешней сортировки в данном разделе рассмотрен только метод сортировки слиянием, позволяющий объединить несколько отсортированных файлов в один.

Временная сложность алгоритмов приводится без доказательства.