Автоматическая обработка текста Представление текстового массива

Способы и форматы представления Способы и форматы представления Индекс Индекс Базы данных Базы данных

Полнотекстовый поиск char* strstr(char *big, char *little) { char *x, *y, *z; for (x = big; *x; x++) { for (y = little, z = x; *y; ++y, ++z) { if (*y != *z) break;} if (!*y) return x; } return 0; } В этой функции языка C текст строки big просматривают слева направо и для каждой позиции x запускают последовательное сравнение с искомой подстрокой little. Для этого, двигая одновременно два указателя y и z, попарно сравнивают все символы. Если мы успешно дошли до конца искомой подстроки, значит она найдена.

Полнотекстовый поиск Найти: «дом» Найти: «дом» ??? Как найти дома, доме, домом и т.п.? ??? Как найти дома, доме, домом и т.п.? форму «дом» или часть слова, совпадающего с последовательностью букв «дом» - народом форму «дом» или часть слова, совпадающего с последовательностью букв «дом» - народом Программа ищет ту подстроку, которую мы ей зададим (точное совпадение) Программа ищет ту подстроку, которую мы ей зададим (точное совпадение) Можно загрузить текст в Word искать там: Правка: найти Что найдем? Можно использовать специальный язык «дом.*» Что найдем? Дома, доме и т.п. + домашний, домовой, домолоть … Дома, доме и т.п. + домашний, домовой, домолоть …

Индекс. Полнотекстовый поиск Хотя прямой просмотр всех текстов – довольно медленное занятие, не следует думать, что алгоритмы прямого поиска не применяются в интернете. Норвежская поисковая система Fast ( использовала чип, реализующий логику прямого поиска упрощенных регулярных выражений [fastpmc], и разместила 256 таких чипов на одной плате. Это позволяло Fast-у обслуживать довольно большое количество запросов в единицу времени. (И. Сегалович)

«Загадки» (backtracking) Поиск в корпусах Лидса: Поиск в корпусах Лидса: Как найти: «Пока!» Как найти: «Пока!» Поиск в COCA Поиск в COCA Найти все формы глагола «tell» Найти все формы глагола «tell» Поиск в НКРЯ: Поиск в НКРЯ: Как найти слова, начинающиеся на пере- и заканчивающиеся на –вываться Как найти слова, начинающиеся на пере- и заканчивающиеся на –вываться ПОЧЕМУ ТАК? ПОЧЕМУ ТАК?

Что после токена? Как представлять аннотации? Как представлять аннотации? Как хранить аннотации? Как хранить аннотации? Как обеспечить навигацию по корпусу (аннотациям) Как обеспечить навигацию по корпусу (аннотациям)

«Упаковка» корпуса. XML разметка

«Упаковка» корпуса. Разметка line line Он synt_tag= gov_by= antec= 1 Он synt_tag= gov_by= antec= 2 так synt_tag= gov_by= antec= 2 так synt_tag= gov_by= antec= 3 любит synt_tag= gov_by= antec= 3 любит synt_tag= gov_by= antec= 4 эту synt_tag= gov_by= antec= 4 эту synt_tag= gov_by= antec= 5 квартиру. synt_tag= gov_by= antec= 5 квартиру. synt_tag= gov_by= antec= line line Судьба synt_tag= gov_by= antec= 1 Судьба synt_tag= gov_by= antec= 2 дала synt_tag= gov_by= antec= 2 дала synt_tag= gov_by= antec= 3 мне synt_tag= gov_by= antec= 3 мне synt_tag= gov_by= antec= 4 эту synt_tag= gov_by= antec= 4 эту synt_tag= gov_by= antec= 5 возможность. synt_tag= gov_by= antec= 5 возможность. synt_tag= gov_by= antec=

Индекс. Инвертированный файл Эта простейшая структура данных. Знакома любому грамотному человеку, так и любому программисту баз данных, даже не имевшему дело с полнотекстовым поиском. Первая категория людей знает, что это такое, по «конкордансам» - алфавитно упорядоченным исчерпывающим спискам слов из одного текста или принадлежащих одному автору (например «Конкорданс к стихам А. С. Пушкина», «Словарь-конкорданс публицистики Ф. М. Достоевского»). Вторые имеют дело с той или иной формой инвертированного списка всякий раз, когда строят или используют «индекс БД по ключевому полю».

% wordtagmorphedgeparent secedge comment % wordtagmorphedgeparent secedge comment #BOS #BOS MцgenVMFIN3.Pl.Pres.KonjHD508 MцgenVMFIN3.Pl.Pres.KonjHD508 PuristenNNMasc.Nom.Pl.*NK505 PuristenNNMasc.Nom.Pl.*NK505 allerPIDAT*.Gen.PlNK500 allerPIDAT*.Gen.PlNK500 MusikbereicheNNMasc.Gen.Pl.*NK500 MusikbereicheNNMasc.Gen.Pl.*NK500 auchADV--MO508 auchADV--MO508 dieARTDef.Fem.Akk.SgNK501 dieARTDef.Fem.Akk.SgNK501 NaseNNFem.Akk.Sg.*NK501 NaseNNFem.Akk.Sg.*NK501 rьmpfenVVINF--HD506 rьmpfenVVINF--HD506,$,----0,$,----0 #500NP--GR505 #500NP--GR505 #501NP--OA506 #501NP--OA506 #EOS 1 #EOS 1

Полнотекстовый поиск vs. ??? Как устроена навигация по книгам? Как устроена навигация по книгам? индекс

Индекс

Индекс. Немного об информационном поиске Which plays of Shakespeare contain the words B RUTUS AND C AESAR, but not C ALPURNIA ? Which plays of Shakespeare contain the words B RUTUS AND C AESAR, but not C ALPURNIA ? One could grep all of Shakespeares plays for B RUTUS and C AESAR, then strip out lines containing CALPURNIA One could grep all of Shakespeares plays for B RUTUS and C AESAR, then strip out lines containing CALPURNIA Why is grep not the solution? Why is grep not the solution? Slow (for large collections) Slow (for large collections) grep is line-oriented, IR is document-oriented grep is line-oriented, IR is document-oriented NOT C ALPURNIA is non-trivial NOT C ALPURNIA is non-trivial Other operations (e.g., find the word R OMANS near COUNTRYMAN ) not feasible Other operations (e.g., find the word R OMANS near COUNTRYMAN ) not feasible

Индекс. Немного об информационном поиске Entry is 1 if term occurs. Example: CALPURNIA occurs in Julius Caesar. Entry is 0 if term doesnt occur. Example: CALPURNIA doesnt occur in The tempest.

16 Incidence vectors So we have a 0/1 vector for each term. To answer the query B RUTUS AND C AESAR AND NOT C ALPURNIA : Take the vectors for B RUTUS, C AESAR AND NOT C ALPURNIA Complement the vector of C ALPURNIA Do a (bitwise) and on the three vectors AND AND =

17 0/1 vector for B RUTUS 17 Anthony and Cleopatra Julius Caesar The Tempest HamletOthelloMacbeth... ANTHON Y BRUTUS CAESAR CALPURN IA CLEOPAT RA MERCY WORSER result:100100

18 Cant build the incidence matrix M = 500,000 × 10 6 = half a trillion 0s and 1s. But the matrix has no more than one billion 1s. Matrix is extremely sparse. What is a better representations? We only record the 1s. 18

19 Inverted Index For each term t, we store a list of all documents that contain t. 19 dictionary postings

20 Inverted Index For each term t, we store a list of all documents that contain t. 20 dictionary postings

Inverted index construction Collect the documents to be indexed: Tokenize the text, turning each document into a list of tokens: Do linguistic preprocessing, producing a list of normalized tokens, which are the indexing terms: Index the documents that each term occurs in by creating an inverted index, consisting of a dictionary and postings. 21

22 Generate posting 22

23 Sort postings 23

24 Create postings lists, determine document frequency 24

25 Split the result into dictionary and postings file 25 dictionary postings

26 Later in this course Index construction: how can we create inverted indexes for large collections? How much space do we need for dictionary and index? Index compression: how can we efficiently store and process indexes for large collections? Ranked retrieval: what does the inverted index look like when we want the best answer? 26

Outline Introduction Inverted index Processing Boolean queries Query optimization 27

28 Simple conjunctive query (two terms) Consider the query: B RUTUS AND C ALPURNIA To find all matching documents using inverted index: Locate B RUTUS in the dictionary Retrieve its postings list from the postings file Locate C ALPURNIA in the dictionary Retrieve its postings list from the postings file Intersect the two postings lists Return intersection to user 28

29 Intersecting two posting lists This is linear in the length of the postings lists. Note: This only works if postings lists are sorted. 29