6. Нечеткий поиск – специфика и функциональное расширение PostgreSQL Виды(категории) фильмов: CREATE TABLE genres (name text UNIQUE, position integer); - презентация

1 6. Нечеткий поиск – специфика и функциональное расширение PostgreSQL Виды(категории) фильмов: CREATE TABLE genres (name text UNIQUE, position integer); Фильмы: CREATE TABLE movies (movie_id SERIAL PRIMARY KEY, title text,genre cube); Актеры: CREATE TABLE actors (actor_id SERIAL PRIMARY KEY, name text); Актеры в фильмах: CREATE TABLE movies_actors (movie_id integer REFERENCES movies NOT NULL, actor_id integer REFERENCES actors NOT NULL, UNIQUE (movie_id, actor_id)); CREATE INDEX movies_actors_movie_id ON movies_actors (movie_id); CREATE INDEX movies_actors_actor_id ON movies_actors (actor_id); CREATE INDEX movies_genres_cube ON movies USING gist (genre);

2 Movies *movie_id title genres [ ] Actors *actor_id name Genres name position Отношение : Разрешить в системе полнотекстный поиск – значит позволить вводить неточные данные: "Forrest Gump "Forest Cump "Aaron Eckhart "Aron Eckhart "A. Eckhart … Переход от РСУБД к NoSQL СУБД Таблица фильмов Таблица жанров Поле-массив, которым соответствует конкретный фильм Таблица списка актеров Movies_actors movie_id actor_id Таблица посредник, обеспечивающая отношение многое-ко-многому Содержимое таблиц в файле: movies_data.sql

3 6.1. Нечеткий поиск в стандарте SQL Операторы LIKE и ILIKE (с учетом и без учета регистров) % - сопоставляется с произвольным числом символов, _ - сопоставляется ровно с одним символом. SELECT title FROM movies WHERE title ILIKE 'stardust%'; SELECT title FROM movies WHERE title ILIKE 'stardust_%';

4 Регулярные выражения, используется в том числе и в NoSQL СУБД. PostgreSQL придерживается синтаксиса регулярных выражений, описанный в стандарте POSIX. В PostgreSQL для сопоставления с регулярными выражениями применяются поператоры: ! - означает несоответствие, *- без учета регистров. Строка заключенная в кавычки – регулярное выражение. Текстовые столбцы выражений можно проиндексировать создав специальный индекс: CREATE INDEX i1 ON movies (lower ( title ) TEXT_PATTERN_OPS ); Подсчет фильмов, которые не начинаются словом the без учета регистров: SELECT Count(*) FROM movies WHERE title !~*'the.*'; Индекс поператорного класса для текстовых полей, значения которых представлены в нижнем регистре. Класс TEXT_PATTERN_OPS возможен для полей с типом TEXT(в нашем случае это поле title), для других типов varchar, char name… - VARCHAR_PATTERN_OPS, BPCHAR_PATTERN_OPS? namechar_pattern_ops…

5 Расстояние Левенштейна. Расстояние Левенштейна – это мера похожести двух строк. Расстояние Левенштейна определяет сколько шагов надо выполнить, чтобы одну строку преобразовать в другую. Шагом считается: замена символа, добавление символа, удаление символа, изменение регистра. Выполним запрос: SELECT * FROM movies WHERE levenshtein ( lower ( title ), lower ('a hard day nght ) ) <= 3 ;

6 Триграммы. Триграммой называется группа из трех последовательный символов в строке поиска. Дополнительная функция show_trgm(…) выделяет из строки все возможные триграммы: Поиск наиболее подходящей строки сводится к подсчету количества совпадающих триграмм. Чем больше совпадений, тем более искомая строка соответствует аргументу поиска. Данный метод поиска полезен при задании аргумента поиска, не обремененного сложностями семантики метасимволов: 1. При поиске строки, игнорируя мелкие несоответствия в орфографии, 2. При проуск коротких фрагментов искомой строки, 3. Когда длина аргумента схожа с длиной искомой строки. 4. При игнорировании регистр символов. Чем длиннее строка, тем больше в ней триграмм, тем вероятнее совпадения и больше количества найденных строк.

7 1. Проверить выполнение дополнительного модуля pg_trgm.sgl: 2. Создать индекс по названиям фильмов General Index Search Tree (GIST, обобщенное индексное дерево поиска ): CREATE INDEX movies_title_trigram ON movies USING gist (title gist_trgm_ops); 3. Использовать триграмму для поиска:

8 Полнотекстный поиск (поиск текстового выражения, когда известны только отдельные фрагменты(слова)) Использование поператора запроса Пример полнотекстового движка поиска. Оператор преобразует поле названия фильма в тип tsvector, а сам запрос – в тип tsquery. Тип данных tsvector представляет строку в виде массива(вектора) лексем, которые сравниваются со строкой, указанной в запросе, а тип запроса tsquery представляет запрос на некотором естественном языке, например, английском или французском. Языку соответствует словарь. Таким образом запрос эквивалентен: SELECT title FROM movies WHERE to_tsvector(title) to_tsquery('english', 'night & day'); Вектор и запрос разбиваются на компоненты: SELECT to_tsvector('A Hard Day''s Night'), to_tsquery('english','night & day');

9 Искать по часто встречаемым (стоп-слова - stopword) сочетаниям (a, the,…) нет смысла, поэтому для нормализации запроса, то есть выделения из него только значимых компонент, анализатор использует соответствующий словарь. Используя другие словари можно расширить поиск: SELECT title FROM movies WHERE to_tsvector(title) to_tsquery('russian','в'); Узнать установленную конфигурацию(языки) : \dF; Для вычисления вектора лексем PostgreSQL использует: 1.Словари, 2. Списки стоп-слов, 3. Анализаторы и шаблоны, которые устанавливают дополнительные правила. Узнать установленные расширения: \dFd; Любой словарь можно протестировать с помощью функции ts_lexize()^ SELECT ts_lexize(english_stem,Days); SELECT ts_lexize(russian,что ты можно сделать?);

10 Полнотекстный поиск настоятельно требует, чтобы таблицы были проиндексированы, иначе он будет выполняться очень медленно. Используя команду выполнения плана запроса EXPLAIN можно получить детали выполнения запроса и увидеть Seq scan…, что говорить о полной сканировании таблицы, то есть чтении каждой строки. Существуют различные типы индексов, среди которых для данной ситуации подходит индекс по значениям лексем типа GIN(Generalized Inverted iNdex). Как и индекс GIST, он встроен в ядро СУБД. Слово инвартированный используется во многих поисковых системах, например Lucene, Sphinx…для полнотекстового поиска. Создать индекс: CREATE INDEX movies_title_searchable ON movies USING gin(to_tsvector('english',title)); Если снова выполнить запрос, то ничего не поменяется: Причина – что индекс GIN строится под конкретный язык, а в команде он не указан. КОМАНДУ EXPLAIN ЦЕЛЕСООБРАЗНО ИСПОЛЬЗОВАТЬ ДЛЯ ПРОВЕРКИ ЭФФЕКТИВНСТИ ПРИМЕННЕНИЯ ИНДЕКСОВ, ТАК КАК НЕЭФФЕКТИВНЫЙ ИНДЕКС - ЛИШНЯЯ НАГРУЗКА НА СУБД.

11

12 Примеры из практики менеджмента и экономики:

13

14 SELECT INN.* FROM INN WHERE INN LIKE *про&тис* ; или SELECT INN.* FROM INN WHERE INN LIKE *про&тис* SELECT COUNT(*) FROM INNN WHERE INN.NAME !~* ^про.*;

15 Расстояние Левенштейна SELECT levenshtein (проeртис, проиртиc) проeртис, levenshtein (проeртис, Пропиртис) Пропиртис, levenshtein (проeртис, проиртис) проиртис, levenshtein (проeртис, проeртис) проeртис; Результат: проиртиc Пропиртиспроиртиспроeртис 2210 SELECT INN.NAME FROM INN WHERE levenstein (lower (NAME), lower (Пропиртис)) <= 1;

16 SELECT show_tgrm (проeртис); show_trgm { п, пр, про, роп, попе, пер, арт, рти, тис, из, з } SELECT INN.NAME FROM INN WHERE NAME % Пропиртис Триграммы:

17 Метафоны Алгоритм мегафонов, в отличии от всех предшествующих вариантов поиска, в которых были заложены снижение требований к синтаксису аргумента(задание образцов LIKE, небольшие орфографические ошибки – расстояние Левенштейна, триграммы позволяют игнорировать разумные ошибки, полнотекстный поиск – игнорировать малозначительные слова, междометья, слова паразиты и пр. а также использовать корень слова, например понимать множественные формы), основан на генерации строкового представления звучания слова. При написании имени актера Брюса Уиллиса (Bruce Willis): SELECT * FROM actors WHERE name = Broos Wilis; SELECT * FROM actors WHERE name % Broos Wilis; - триграмма не поможет Метафоны реализуются поператором функции metaphon()/ Дополнительно используем NATURAL JON – который соответствует INNER JOIN, в котором соединение автоматически производится по столбцам с одинаковыми именами:

18 В модуле f uzzystrmatch.sql есть набор функций, с помощью которых можно вычислять метафоры: metaphone (text, int); dmetaphone (text); - двойной мегафон; dmetaphone_alt (text) – для альтернативного произношения; soundex(text); - алгоритм 1880-годов для сравнения типичных американских фамилий при переписи в США.

19 Выполним: SELECT title FROM movies NATURAL JOIN movies_actors NATURAL JOIN actors WHERE metaphone(name,6) % metaphone('Broos Wils',6);

20 Если сравнить эффективность функций, то она примерно одинакова: SELECT name, metaphone(name,8),dmetaphone(name),dmetaphone_alt(name),soundex(name) FROM actors;

21 Комбинирование различных способов Так как метафоры возвращают строковые значения, то их можно использовать в сочетании с другими методами поиска строк. SELECT * FROM actors WHERE metaphone(name,8) % metaphone('Robin Williams',8); Например, строку, возвращенную функцией metaphone(), можно разложить на триграммы, а затем упорядочить по наименьшему расстоянию Левенштейна: FROM actors WHERE metaphone(name,8) % metaphone('Robin Williams',8) ORDER BY levenshtein(lower('Robin Williams'),lower(name)); Следует помнить об осторожности бесконтрольного использования комбинированных результатов

22 Поиск по ближайшему соответствию (многомерные запросы PostrgreSQL, MongoDB…) Дополнительный пакет cube.sql содержит методы эффективного поиска, основанные на поиске ближайших точек в пределах куба – особого типа данных в виде многомерного вектора. Идея заключается что в двумерном пространстве(вселенной) для поиска вероятного соответствия нужно искать ближайшего соседа: искать пять ближайших городов на карте области быстрее, чем на карте РФ или земли. Создать запрос, в котором выбрать фильмы: 1. приключение – 7 ( каждом жанре присваивается рейтинг от 0 до 10), 2. вестерны -7, 3.научная-фантастика -10(SELECT * FROM genres;). Пример для фильма «Звездные войны»: SELECT name, cube_ur_coord('(0,7,0,0,0,0,0,0,0,7,0,0,0,0,10,0,0,0)',position) as score FROM genres WHERE cube_ur_coord('(0,7,0,0,0,0,0,0,0,7,0,0,0,0,10,0,0,0)', position) >0;

23 Аналогичные использование жанров: - присвоение характеристик сотрудникам в аудите и консалтинге, например: касса, МСФО, налоги, документация, оценка интеллектуальной собственности, международное законодательство, оценка бизнеса, основные средства, …) -аутсорсинговые компании в области ИТ(специалисты в области администрирования сетей, постановщики, тестировщики, разработчики интернет –сервисов, разработчики приложений на основе языков высокого уровня, администраторы баз данных, разработчики приложения на основе баз данных…), --классификация счетов-фактур (авансы, выполнение этапов договора, оценка, консультации, аудит, информационное сопровождение,…), то есть найти группу предприятий, которым выполнялись консалтинговые услуги аналогичные для ОАО «Лукойл». cube_ur_coord – функция свартывания вектора(например, как в примере, жанров) cube_distance(poin1, point2); - функция поиска ближайшего соседа: SELECT *, cube_distance(genre,'(0,7,0,0,0,0,0,0,0,7,0,0,0,0,10,0,0,0)') dist FROM movies ORDER BY dist; Найдем наиболее близкие фильмы:

24 Даже при наличии индекса поиск выполняется крайне медленно, так как происходит сканирование всей таблицы, вычисление расстояние для каждой строки, а затем сортировка результатов. Поэтому можно воспользоваться алгоритмом вычисления вероятностей, чтобы применить ограничивающий куб. Функция cube_enlarge() строит 18-мерный куб с центром в данной точке и стороной заданной длины. Пусть есть двумерный квадрат с центром 1,1 и радиусом 1. Тогда получим, что его левый верхний угол точка 0,0, а правый нижний – 2,2. Воспользовавшись ограничивающим гиперкубом и специальным который означает содержит, найдем фильмы ограничившись кубом со стороной 5: SELECT title, cube_distance(genre,'(0,7,0,0,0,0,0,0,0,7,0,0,0,0,10,0,0,0)') dist FROM movies WHERE genre ORDER BY dist;

25

26 Воспользовавшись подзапросом, можно получить жанр по названию фильма и произвести уже вычисления для него, воспользовавшись псевдонимом таблицы. то есть, взяв счет-фактура можно найти аналогичные ему, а по ним и организации. SELECT m.movie_id, m.title FROM movies m, (SELECT genre, title FROM movies WHERE title = 'Mad Max') s WHERE cube_enlarge(s.genre,5, m.genre AND s.title <> m.title ORDER BY cube_distance(m.genre, s.genre) LIMIT 10;

27 Тематика КР: Разработать содержимое баз таблиц PostgreSQL для демонстрации инструмента нечеткого поиска в следующих областях: 1. российские и советская кинотека, 2. библиотека зарубежной фантастики, 3. туриндустрия. 4. литература по информационным технологиям и программированию, 5. зарубежные фильмы на российском рынке проката, 6. библиотека российской и советской классики, 7. клиентская база организации, 8. библиотека по экономике и менеджменту, 9. номенклатура продовольственных товаров, 10. винотека 11. …