信息检索四Dictionary剖析.ppt

湖南大学计算机与通信学院 刘钰峰 Recap of the previous lecture Basic inverted indexes: Structure: Dictionary and Postings Key step in construction: Sorting Boolean query processing Simple optimization Linear time merging Recall basic indexing pipeline Parsing a document What format is it in? pdf/word/excel/html? What language is it in? What character set is in use? Complications: Format/language Documents being indexed can include docs from many different languages A single index may have to contain terms of several languages. Sometimes a document or its components can contain multiple languages/formats French email with a German pdf attachment. What is a unit document? A file? An email? (Perhaps one of many in an mbox.) An email with 5 attachments? A group of files (PPT or LaTeX in HTML) Tokenization Input: “Friends, Romans and Countrymen” Output: Tokens Friends Romans Countrymen Tokenization；把字符串变为词串。 Each such token is now a candidate for an index entry, after further processing Described below Lemmatization：对词进行内部结构和形式分析。 But what are valid tokens to emit? （1）对一个待分析的字符串（S），从左到右进行扫描，读入当前字符（char）到候选词数组（W[ i ]），并将指针（pointer）前移，i=i+1； （2）看char是否为词分隔符（事先可以预定义空格以及一般标点均为词分隔符）； （3）如果char是词分隔符，并且W不是空格，将W中从起始位置到i-1位置的字符作为一个词汇单位输出，同时将S中的W部分删去，然后清空W，转入（1），如果char是词分隔符，且W是空格，将S中的W部分删去，清空W，转入（1）； （4）如果不是词分隔符，看指针是否已经指到字符流尾部； （5）如果指针已经指到字符流尾部，将当前W从起始位置到i-1位置的字符作为一个词汇单位输出，结束。 （6）如果不是字符流尾部，转入（1）； Tokenization示例 Tokenization : Language issues Issues in tokenization: Finland’s capital ? Finland? Finlands? Finland’s? State-of-the-art: break up hyphenated sequence. co-education ? the hold-him-back-and-drag-him-away-maneuver ? It’s effective to get the user to put in possible hyphens San Francisco: one token or two? How do you decide it is one token? 策略 hyphenated prefixes Encourage users to enter hyphens wherever they may be possible over-eager to search for over-eager OR over eager OR overeager. Tokenization: Language issues Tokenization: other issues 3/12/91 Mar. 12, 1991 55 B.C