Index (search engine) (Wikipedia)

Index (search engine) (Wikipedia)

Search engine indexing entails how data is collected, parsed, and stored to facilitate fast and accurate retrieval. Index design incorporates interdisciplinary concepts from linguistics, cognitive psychology, mathematics, informatics, physics, and computer science. An alternate name for the process is Web indexing, within the context of search engines designed to find web pages on the Internet.

Popular engines focus on the full-text indexing of online, natural language documents^[1], yet there are other searchable media types such as video, audio^[2], and graphics^[3][4]. Meta search engines reuse the indices of other services and do not store a local index, whereas cache-based search engines permanently store the index along with the corpus. Unlike full text indices, partial text services restrict the depth indexed to reduce index size. Larger services typically perform indexing at a predetermined interval due to the required time and processing costs, whereas agent-based search engines index in real time.

Contents 1 Indexing 1.1 Index Design Factors 1.2 Index Data Structures 1.3 Challenges in Parallelism 1.4 Inverted indices 1.5 Index Merging 1.6 The Forward Index 1.7 Compression 2 Document Parsing 2.1 Challenges in Natural Language Processing 2.2 Tokenization 2.3 Language Recognition 2.4 Format Analysis 2.5 Section Recognition 2.6 Meta Tag Indexing 3 See also 4 Further reading 5 References

Indexing

The goal of storing an index is to optimize the speed and performance of finding relevant documents for a search query. Without an index, the search engine would scan every document in the corpus, which would take a considerable amount of time and computing power. For example, an index of 10,000 documents can be queried within milliseconds, where a sequential scan of every word in 10,000 large documents could take hours. No search engine user would be comfortable waiting several hours to get search results. The trade off for the time saved during retrieval is that additional storage is required to store the index and that it takes a considerable amount of time to update.

Index Design Factors

Major factors in designing a search engine's architecture include:

Merge factors

How data enters the index, or how words or subject features are added to the index during corpus traversal, and whether multiple indexers can work asynchronously. The indexer must first check whether it is updating old content or adding new content. Traversal typically correlates to the data collection policy. Search engine index merging is similar in concept to the SQL Merge command and other merge algorithms.^[5]

Storage techniques

How to store the index data - whether information should be compressed or filtered

Index size

How much computer storage is required to support the index

Lookup speed

How quickly a word can be found in the inverted index. How quickly an entry in a data structure can be found, versus how quickly it can be updated or removed, is a central focus of computer science

Maintenance

Maintaining the index over time^[6]

Fault tolerance

How important it is for the service to be reliable, how to deal with index corruption, whether bad data can be treated in isolation, dealing with bad hardware, partitioning schemes such as hash-based or composite partitioning^[7], replication

Index Data Structures

Search engine architectures vary in how indexing is performed and in index storage to meet the various design factors. Types of indices include:

Suffix trees

Figuratively structured like a tree, supports linear time lookup. Built by storing the suffixes of words. Used for searching for patterns in DNA sequences and clustering. A major drawback is that the storage of a word in the tree may require more storage than storing the word itself.^[8] An alternate representation is a suffix array, which is considered to require less memory and supports compression like BWT.

Trees

An ordered tree data structure that is used to store an associative array where the keys are strings. Regarded as faster than a hash table, but are less space efficient. The suffix tree is a type of trie. Tries support extendible hashing, which is important for search engine indexing.^[9]

Inverted indices

Stores a list of occurrences of each atomic search criterion^[10], typically in the form of a hash table or binary tree^[11][12].

Citation indices

Stores the existence of citations or hyperlinks between documents to support citation analysis, a subject of Bibliometrics.

Ngram indices

For storing sequences of n length of data to support other types of retrieval or text mining.^[13]

Term document matrices

Used in latent semantic analysis, stores the occurrences of words in documents in a two dimensional sparse matrix.

Challenges in Parallelism

A major challenge in the design of search engines is the management of parallel processes. There are many opportunities for race conditions and coherence faults. For example, a new document is added to the corpus and the index must be updated, but the index simultaneously needs to continue responding to search queries. This is a collision between two competing tasks. Consider that authors are producers of information, and a crawler is the consumer of this information, grabbing the text and storing it in a cache (or corpus). The forward index is the consumer of the information produced by the corpus, and the inverted index is the consumer of information produced by the forward index. This is commonly referred to as a producer-consumer model. The indexer is the producer of searchable information and users are the consumers that need to search. The challenge is magnified when working with distributed storage and distributed processing. In an effort to scale with larger amounts of indexed information, the search engine's architecture may involve distributed computing, where the search engine consists of several machines operating in unison. This increases the possibilities for incoherency and makes it more difficult to maintain a fully-synchronized, distributed, parallel architecture.^[14]

Inverted indices

Many search engines incorporate an inverted index when evaluating a search query to quickly locate the documents which contain the words in a query and rank these documents by relevance. The inverted index stores a list of the documents for each word. The search engine can retrieve the matching documents quickly using direct access to find the documents for a word. The following is a simplified illustration of the inverted index:

Inverted Index

Word	Documents
the	Document 1, Document 3, Document 4, Document 5
cow	Document 2, Document 3, Document 4
says	Document 5
moo	Document 7

The above figure is a simplified form of a Boolean index. Such an index would only serve to determine whether a document matches a query, but would not contribute to ranking matched documents. In some designs the index includes additional information such as the frequency of each word in each document or the positions of the word in each document.^[15] With position, the search algorithm can identify word proximity to support searching for phrases. Frequency can be used to help in ranking the relevance of documents to the query. Such topics are the central research focus of information retrieval.

The inverted index is a sparse matrix given that words are not present in each document. It is stored differently than a two dimensional array to reduce memory requirements. The index is similar to the term document matrices employed by latent semantic analysis. The inverted index can be considered a form of a hash table. In some cases the index is a form of a binary tree, which requires additional storage but may reduce the lookup time. In larger indices the architecture is typically distributed.^[16]

Inverted indices can be programmed in several computer programming languages.^[17][18]

Index Merging

The inverted index is filled via a merge or rebuild. A rebuild is similar to a merge but first deletes the contents of the inverted index. The architecture may be designed to support incremental indexing^[19], where a merge involves identifying the document or documents to add into or update in the index and parsing each document into words. For technical accuracy, a merge involves the unison of newly indexed documents, typically residing in virtual memory, with the index cache residing on one or more computer hard drives.

After parsing, the indexer adds the containing document to the document list for the appropriate words. The process of finding each word in the inverted index in order to denote that it occurred within a document may be too time consuming when designing a larger search engine, and so this process is commonly split up into the development of a forward index and the process of sorting the contents of the forward index for entry into the inverted index. The inverted index is named inverted because it is an inversion of the forward index.

The Forward Index

The forward index stores a list of words for each document. The following is a simplified form of the forward index:

Forward Index

Document	Words
Document 1	the,cow,says,moo
Document 2	the,cat,and,the,hat
Document 3	the,dish,ran,away,with,the,spoon

The rationale behind developing a forward index is that as documents are parsed, it is better to immediately store the words per document. The delineation enables asynchronous processing, which partially circumvents the inverted index update bottleneck.^[20] The forward index is sorted to transform it to an inverted index. The forward index is essentially a list of pairs consisting of a document and a word, collated by the document. Converting the forward index to an inverted index is only a matter of sorting the pairs by the words. In this regard, the inverted index is a word-sorted forward index.

Compression

Generating or maintaining a large-scale search engine index represents a significant storage and processing challenge. Many search engines utilize a form of compression to reduce the size of the indices on disk.^[21] Consider the following scenario for a full text, Internet, search engine.

• An estimated 2,000,000,000 different web pages exist as of the year 2000^[22]


• A fictitious estimate of 250 words per webpage on average, based on the assumption of being similar to the pages of a novel.^[23]


• It takes 8 bits (or 1 byte) to store a single character. Some encodings use 2 bytes per character^[24][25]


• The average number of characters in any given word on a page can be estimated at 5 (Wikipedia:Size comparisons)


• The average personal computer comes with about 20 gigabytes of usable space^[26]

Given these estimates, generating an uncompressed index (assuming a non-conflated, simple, index) for 2 billion web pages would need to store 5 billion word entries. At 1 byte per character, or 5 bytes per word, this would require 2500 gigabytes of storage space alone, more than the average size a personal computer's free disk space. This space is further increased in the case of a distributed storage architecture that is fault-tolerant. Using compression, the index size can be reduced to a portion of its size, depending on which compression techniques are chosen. The trade off is the time and processing power required to perform compression and decompression.

Notably, large scale search engine designs incorporate the cost of storage, and the costs of electricity to power the storage. Compression, in this regard, is a measure of cost as well.

Document Parsing

Document parsing involves breaking apart the components (words) of a document or other form of media for insertion into the forward and inverted indices. For example, if the full contents of a document consisted of the sentence "Hello World", there would typically be two words found, the token "Hello" and the token "World". In the context of search engine indexing and natural language processing, parsing is more commonly referred to as tokenization, and sometimes word boundary disambiguation, tagging, text segmentation, content analysis, text analysis, text mining, concordance generation, Speech segmentation, lexing, or lexical analysis. The terms 'indexing', 'parsing', and 'tokenization' are used interchangeably in corporate slang.

Natural language processing, as of 2006, is the subject of continuous research and technological improvement. There are a host of challenges in tokenization, in extracting the necessary information from documents for indexing to support quality searching. Tokenization for indexing involves multiple technologies, the implementation of which are commonly kept as corporate secrets.

Challenges in Natural Language Processing

Word Boundary Ambiguity - native English speakers can at first consider tokenization to be a straightforward task, but this is not the case with designing a multilingual indexer. In digital form, the text of other languages such as Chinese, Japanese or Arabic represent a greater challenge as words are not clearly delineated by whitespace. The goal during tokenization is to identify words for which users will search. Language specific logic is employed to properly identify the boundaries of words, which is often the rationale for designing a parser for each language supported (or for groups of languages with similar boundary markers and syntax).

Language Ambiguity - to assist with properly ranking matching documents, many search engines collect additional information about words, such as its language or lexical category (part of speech). These techniques are language-dependent as the syntax varies among languages. Documents do not always clearly identify the language of the document or represent it accurately. In tokenizing the document, some search engines attempt to automatically identify the language of the document.

Diverse File Formats - in order to correctly identify what bytes of a document represent characters, the file format must be correctly handled. Search engines which support multiple file formats must be able to correctly open and access the document and be able to tokenize the characters of the document.

Faulty Storage - the quality of the natural language data is not always assumed to be perfect. An unspecified amount of documents, particular on the Internet, do not always closely obey proper file protocol. binary characters may be mistakenly encoded into various parts of a document. Without recognition of these characters and appropriate handling, the index quality or indexer performance could degrade.

Tokenization

Unlike literate human adults, computers are not inherently aware of the structure of a natural language document and do not instantly recognize words and sentences. To a computer, a document is only a big sequence of bytes. Computers do not know that a space character between two sequences of characters means that there are two separate words in the document. Instead, a computer program is developed by humans which trains the computer, or instructs the computer, how to identify what constitutes an individual or distinct word, referred to as a token. This program is commonly referred to as a tokenizer or parser or lexer. Many search engines, as well as other natural language processing software, incorporate specialized programs for parsing, such as YACC OR Lex.

During tokenization, the parser identifies sequences of characters, which typically represent words. Commonly recognized tokens include punctuation, sequences of numerical characters, alphabetical characters, alphanumerical characters, binary characters (backspace, null, print, and other antiquated print commands), whitespace (space, tab, carriage return, line feed), and entities such as email addresses, phone numbers, and URLs. When identifying each token, several characteristics may be stored such as the token's case (upper, lower, mixed, proper), language or encoding, lexical category (part of speech, like 'noun' or 'verb'), position, sentence number, sentence position, length, and line number.

Language Recognition

If the search engine supports multiple languages, a common initial step during tokenization is to identify each document's language, given that many of the later steps are language dependent (such as stemming and part of speech tagging). Language recognition is the process by which a computer program attempts to automatically identify, or categorize, the language of a document. Other names for language recognition include language classification, language analysis, language identification, and language tagging. Automated language recognition is the subject of ongoing research in natural language processing. Finding which language the words belongs to may involve the use of a language recognition chart.

Format Analysis

Depending on whether the search engine supports multiple document formats, documents must be prepared for tokenization. The challenge is that many document formats contain, in addition to textual content, formatting information. For example, HTML documents contain HTML tags, which specify formatting information, like whether to start a new line, or display a word in bold, or change the font size or family. If the search engine were to ignore the difference between content and markup, the segments would also be included in the index, leading to poor search results. Format analysis involves the identification and handling of formatting content embedded within documents which control how the document is rendered on a computer screen or interpreted by a software program. Format analysis is also referred to as structure analysis, format parsing, tag stripping, format stripping, text normalization, text cleaning, or text preparation. The challenge of format analysis is further complicated by the intricacies of various file formats. Certain file formats are proprietary and very little information is disclosed, while others are well documented. Common, well-documented file formats that many search engines support include:

• Microsoft Word


• Microsoft Excel


• Microsoft Powerpoint


• IBM Lotus Notes


• HTML


• ASCII text files (a text document without any formatting)


• Adobe's Portable Document Format (PDF)


• PostScript (PS)


• LaTex


• The UseNet archive (NNTP) and other deprecated bulletin board formats


• XML and derivatives like RSS


• SGML (this is more of a general protocol)


• Multimedia meta data formats like ID3

Techniques for dealing with various formats include:

• Using a publicly available commercial parsing tool that is offered by the organization which developed, maintains, or owns the format


• Writing a custom parser

Some search engines support inspection of files that are stored in a compressed, or encrypted, file format. If working with a compressed format, then the indexer first decompresses the document, which may result in one or more files, each of which must be indexed separately. Commonly supported compressed file formats include:

• ZIP - Zip File


• RAR - Archive File


• CAB - Microsoft Windows Cabinet File


• Gzip - Gzip file


• BZIP - Bzip file


• TAR, GZ, and TAR.GZ - Unix Gzip'ped Archives

Format analysis can involve quality improvement methods to avoid including 'bad information' in the index. Content can manipulate the formatting information to include additional content. Examples of abusing document formatting for spamdexing:

• Including hundreds or thousands of words in a section which is hidden from view on the computer screen, but visible to the indexer, by use of formatting (e.g. hidden "div" tag in HTML, which may incorporate the use of CSS or Javascript to do so).


• Setting the foreground font color of words to the same as the background color, making words hidden on the computer screen to a person viewing the document, but not hidden to the indexer.

Section Recognition

Some search engines incorporate section recognition, the identification of major parts of a document, prior to tokenization. Not all the documents in a corpus read like a well-written book, divided into organized chapters and pages. Many documents on the web contain erroneous content and side-sections which do not contain primary material, that which the document is about, such as newsletters and corporate reports. For example, this article may display a side menu with words inside links to other web pages. Some file formats, like HTML or PDF, allow for content to be displayed in columns. Even though the content is displayed, or rendered, in different areas of the view, the raw markup content may store this information sequentially. Words that appear in the raw source content sequentially are indexed sequentially, even though these sentences and paragraphs are rendered in different parts of the computer screen. If search engines index this content as if it were normal content, a dilemma ensues where the quality of the index is degraded and search quality is degraded due to the mixed content and improper word proximity. Two primary problems are noted:

• Content in different sections is treated as related in the index, when in reality it is not


• Organizational 'side bar' content is included in the index, but the side bar content does not contribute to the meaning of the document, and the index is filled with a poor representation of its documents, assuming the goal is to go after the meaning of each document, a sub-goal of providing quality search results.

Section analysis may require the search engine to implement the rendering logic of each document, essentially an abstract representation of the actual document, and then index the representation instead. For example, some content on the Internet is rendered via Javascript. Viewers of web pages in web browsers see this content. If the search engine does not render the page and evaluate the Javascript within the page, it would not 'see' this content in the same way, and index the document incorrectly. Given that some search engines do not bother with rendering issues, many web page designers avoid displaying content via Javascript or use the Noscript tag to ensure that the web page is indexed properly. At the same time, this fact is also exploited to cause the search engine indexer to 'see' different content than the viewer.

Meta Tag Indexing

Specific documents offer embedded meta information such as the author, keywords, description, and language. For HTML pages, the meta tag contains keywords which are also included in the index. During earlier growth periods in the Internet and search engine technology (more so, the hardware on which it runs) would only index the keywords in the meta tags for the forward index (and still applying techniques such as stemming and stop words). The full document would not be parsed. At this time, full-text indexing was not as well established, nor was the hardware to support such technology. The design of the HTML markup language initially included support for meta tags for this very purpose of being properly and easily indexed, without requiring tokenization.^[27]

As the Internet grew (the number of users capable of browsing the web and the number of websites increased and the technology for making websites and hosting websites improved), many brick-and-mortar corporations went 'online' in the mid 1990s and established corporate websites. The keywords used to describe webpages (many of which were corporate-oriented webpages similar to product brochures) changed from descriptive keywords to marketing-oriented keywords designed to drive sales by placing the webpage high in the search results for specific search queries. The fact that these keywords were subjectively-specified was leading to spamdexing, which drove many search engines to adopt full-text indexing technologies in the 1990s. Search engine designers and companies could only place so many 'marketing keywords' into the content of a webpage before draining it of all interesting and useful information. Given that conflict of interest with the business goal of designing user-oriented websites which were 'sticky', the customer lifetime value equation was changed to incorporate more useful content into the website in hopes of retaining the visitor. In this sense, full-text indexing was more objective and increased the quality of search engine results, as it was one more step away from subjective control of search engine result placement, which in turn furthered research of full-text indexing technologies.

In the context of Desktop search, many solutions incorporate meta tags to provide a way for authors to further customize how the search engine will index content from various files that is not evident from the file content. Desktop search is under the control of the user and the changes in that context only serve to help, unlike Internet search engines which must focus more on the full text index.

See also

• Information retrieval


• Document Retrieval


• Information extraction


• Search engine


• Vertical search


• Desktop search
  
  
  
  • Windows indexing service^[28]
  
  
  
  


• List of search engines


• Text Retrieval


• Latent Semantic Indexing


• Keyword In Context Indexing


• Concordance


• Controlled vocabulary


• Natural language processing


• Text mining


• Content analysis

Further reading

• R. Bayer and E. McCreight. Organization and maintenance of large ordered indices. Acta Informatica, 173-189, 1972.


• Donald E. Knuth. The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co. Redwood City, CA, 1997.


• Donald E. Knuth. The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co. Redwood City, CA, 1998.


• Gerald Salton. Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988.


• Gerard Salton. Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986.


• Gerard Salton. Lesk, M.E.: Computer evaluation of indexing and text processing. Journal of the ACM. January 1968.


• Gerard Salton. The SMART Retrieval System - Experiments in Automatic Document Processing. Prentice Hall Inc., Englewood Cliffs, 1971.


• Gerard Salton. The Transformation, Analysis, and Retrieval of Information by Computer, Addison-Wesley, Reading, Mass., 1989.


• Baeza-Yates, R., Ribeiro-Neto, B.: Modern Information Retrieval. Chapter 8. ACM Press 1999.


• G. K. Zipf. Human Behavior and the Principle of Least Effort. Addison-Wesley, 1949.


• Adelson-Velskii, G.M., Landis, E. M.: An information organization algorithm. DANSSSR, 146, 263-266 (1962).


• Edward H. Sussenguth, Jr., Use of tree structures for processing files, Communications of the ACM, v.6 n.5, p.272-279, May 1963


• Harman, D.K., et al: Inverted files. In Information Retrieval: Data Structures and Algorithms, Prentice-Hall, pp 28-43, 1992.


• Lim, L., et al: Characterizing Web Document Change, LNCS 2118, 133-146, 2001.


• Lim, L., et al: Dynamic Maintenance of Web Indexes Using Landmarks. Proc. of the 12th W3 Conference, 2003.


• Moffat, A., Zobel, J.: Self-Indexing Inverted Files for Fast Text Retrieval. ACM TIS, 349-379, October 1996, Volume 14, Number 4.


• Mehlhorn, K.: Data Structures and Efficient Algorithms, Springer Verlag, EATCS Monographs, 1984.


• Mehlhorn, K., Overmars, M.H.: Optimal Dynamization of Decomposable Searching Problems. IPL 12, 93-98, 1981.


• Mehlhorn, K.: Lower Bounds on the Efficiency of Transforming Static Data Structures into Dynamic Data Structures. Math. Systems Theory 15, 1-16, 1981.


• Koster, M.: ALIWEB: Archie-Like indexing in the Web. Computer Networks and ISDN Systems, Vol. 27, No. 2 (1994) 175-182 (also see Proc. First Int'l World Wide Web Conf., Elsevier Science, Amsterdam, 1994, pp. 175-182)


• Serge Abiteboul and Victor Vianu. Queries and Computation on the Web. Proceedings of the International Conference on Database Theory. Delphi, Greece 1997.


• Ian H Witten, Alistair Moffat, and Timothy C. Bell. Managing Gigabytes: Compressing and Indexing Documents and Images. New York: Van Nostrand Reinhold, 1994.


• A. Emtage and P. Deutsch, "Archie--An Electronic Directory Service for the Internet." Proc. Usenix Winter 1992 Tech. Conf., Usenix Assoc., Berkeley, Calif., 1992, pp. 93-110.


• M. Gray, World Wide Web Wanderer.


• D. Cutting and J. Pedersen. "Optimizations for Dynamic Inverted Index Maintenance." Proceedings of the 13th International Conference on Research and Development in Information Retrieval, pp. 405-411, September 1990.


• Searching semantic information

References

1. ^ Clarke, C., Cormack, G.: Dynamic Inverted Indexes for a Distributed Full-Text Retrieval System. TechRep MT-95-01, University of Waterloo, February 1995.


2. ^ Stephen V. Rice, Stephen M. Bailey. Searching for Sounds. Comparisonics Corporation. May 2004. Verified Dec 2006


3. ^ Charles E. Jacobs, Adam Finkelstein, David H. Salesin. Fast Multiresolution Image Querying. Department of Computer Science and Engineering, University of Washington. 1995. Verified Dec 2006


4. ^ Lee, James. Software Learns to Tag Photos. MIT Technology Review. November 09, 2006. Pg 1-2. Verified Dec 2006. Commercial external link


5. ^ Brown, E.W.: Execution Performance Issues in Full-Text Information Retrieval. Computer Science Department, University of Massachusetts at Amherst, Technical Report 95-81, October 1995.


6. ^ Cutting, D., Pedersen, J.: Optimizations for dynamic inverted index maintenance. Proceedings of SIGIR, 405-411, 1990.


7. ^ Linear Hash Partitioning. MySQL 5.1 Reference Manual. Verified Dec 2006


8. ^ Gusfield, Dan [1997] (1999). Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8. .


9. ^ trie, Dictionary of Algorithms and Data Structures, U.S. National Institute of Standards and Technology.


10. ^ Black, Paul E., inverted index, Dictionary of Algorithms and Data Structures, U.S. National Institute of Standards and Technology Oct 2006. Verified Dec 2006.


11. ^ C. C. Foster, Information retrieval: information storage and retrieval using AVL trees, Proceedings of the 1965 20th national conference, p.192-205, August 24-26, 1965, Cleveland, Ohio, United States


12. ^ Landauer, W. I.: The balanced tree and its utilization in information retrieval. IEEE Trans. on Electronic Computers, Vol. EC-12, No. 6, December 1963.


13. ^ Google Ngram Datasets for sale at LDC Catalog


14. ^ Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified Data Processing on Large Clusters. Google, Inc. OSDI. 2004.


15. ^ Grossman, Frieder, Goharian. IR Basics of Inverted Index. 2002. Verified Dec 2006.


16. ^ Tang, Hunqiang. Dwarkadas, Sandhya. "Hybrid Global Local Indexing for Efficient Peer to Peer Information Retrieval". University of Rochester. Pg 1. http://www.cs.rochester.edu/u/sarrmor/publications/eSearch-NSDI.ps


17. ^ [1] - inverted index written in Haskell


18. ^ [2] - inverted index written in Lisp


19. ^ Tomasic, A., et al: Incremental Updates of Inverted Lists for Text Document Retrieval. Short Version of Stanford University Computer Science Technical Note STAN-CS-TN-93-1, December, 1993.


20. ^ Sergey Brin and Lawrence Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Stanford University. 1998. Verified Dec 2006.


21. ^ H.S. Heaps. Storage analysis of a compression coding for a document database. 1NFOR, I0(i):47-61, February 1972.


22. ^ Murray, Brian H. Sizing the Internet. Cyveillance, Inc. Pg 2. July 2000. Verified Dec 2006.


23. ^ Blair Bancroft. Word Count:A Highly Personal-and Probably Controversial-Essay on Counting Words. Personal Website. Verified Dec 2006.


24. ^ The Unicode Standard - Frequently Asked Questions. Verified Dec 2006.


25. ^ Storage estimates. Verified Dec 2006.


26. ^ PC Technology Guide: Guides/Storage/Hard Disks. PC Technology Guide. 2003. Verified Dec 2006.


27. ^ Berners-Lee, T., "Hypertext Markup Language - 2.0", RFC 1866, Network Working Group, November 1995.


28. ^ Krishna Nareddy. Indexing with Microsoft Index Server. MSDN Library. Microsoft Corporation. January 30, 1998. Verified Dec 2006. Note that this is a commercial, external link.

Technorati : Search engine indexing

Tolerant string matching using the Levenshtein algorithm (Code Project)

Tolerant string matching using the Levenshtein algorithm

• Download source code - 11.6 Kb

Introduction

Sometimes it's handy to have a tolerant string matching function which finds almost indentical strings. I needed it in our German receipt database RkSuite to manage the categories which are sometimes just wrongly spelled or which are variations of other categories.

Different algorithms exist to solve this problem, a very common program under Unix is soundex but it's only useful if you stick to one language. If you have English, German, French, ... words the soundex algorithm wouldn't work effectively so a more general approach was required. After some search with Google I heard about Levenshtein.

Background

The code is based on the original work by Michael Gillel, visit his Homepage and read his excellent article about the Levenshtein algorithm. Come back and join me when I show you how to use your new knowledge in your own applications.

Using the code

The class Levenshtein (levenshtein.cpp, levenshtein.h) contains the code which calculates the edit distance between 2 words. The edit distance describes how many edit operations (insert, remove, change) are necessary to transform one string into another. The code uses no sophisticated tricks, any C++ compiler should be able to deal with it.

The method Get returns the edit distance. The plain value may or may not be interesting for you, in my example I use the formula Edit Distance * 100 / string length to tolerate more errors in longer strings.

Two different Get methods are available, the first works with strings with a maximum length of MAXLINE (default: 128). I use static arrays for the calculation which slightly improves the speed of the algorithm. You can change the constant to save memory. Please note that a two-dimensional array will be created which requires MAXLINE * MAXLINE * sizeof(int) bytes.

If you are not sure how long your strings are you can use the method Get2, it allocates the memory dynamically and can deal with (almost) any string length. If a string is too long for the algorithm above, the 2nd one is used automatically.

Usage is very simple:

// calculate Levenshtein distance
Levenshtein lev;
int nError = lev.Get(string1, string2);

// recalculate value
int nNormalizedError = 100 * nError / strlen(string1);

The code in the example uses a small list from the file liste.txt. You can play around with the tolerance setting to see which strings are recognized as similar. The demo project uses the MFC and has been compiled with Visual Studio .NET 2003. It should be easily possible to create a VC6 project, just add all .h, .cpp and .rc files to the project.

Final conclusion

The algorithm works very well for small sets of data (several 1000s). I have tried to use it for spell checking but comparing a string against a dictionary of usual size is not efficient. Anyway, it's incredible to switch from perfect to tolerant matching and your users will be glad that your program gives you a chance to make errors.

Technorati : Levenshtein algorithm

Longest common subsequence problem (Wikipedia)

Longest common subsequence problem (Wikipedia)

Technorati : Longest common subsequence

Longest increasing subsequence problem (Wikipedia)

Longest increasing subsequence problem (Wikipedia)

Technorati : Longest increasing subsequence

Longest common substring problem - Wikipedia, the free encyclopedia

Longest common substring problem - Wikipedia, the free encyclopedia

Levenshtein distance (Wikipedia)

Levenshtein distance

Technorati : Levenshtein algorithm

Full text search (Wikipedia)

Full text search (Wikipedia)

...

Improving the performance of full text searching

The deficiencies of free text searching have been addressed in two ways: By providing users with tools that enable them to express their search questions more precisely, and by developing new search algorithms that improve retrieval precision.

Improved querying tools

• Keywords. Document creators (or trained indexers) are asked to supply a list of words that describe the subject of the text, including synonyms of words that describe this subject. Keywords improve recall, particularly if the keyword list includes a search word that is not in the document text.
• Field-restricted search. Some search engines enable users to limit free text searches to a particular field within a stored data record, such as "Title" or "Author."
• Boolean queries. Searches that use Boolean operators (for example, "encyclopedia" AND "online" NOT "Encarta") can dramatically increase the precision of a free text search. The AND operator says, in effect, "Do not retrieve any document unless it contains both of these terms." The NOT operator says, in effect, "Do not retrieve any document that contains this word." If the retrieval list retrieves too few documents, the OR operator can be used to increase recall; consider, for example, "encyclopedia" AND "online" OR "Internet" NOT "Encarta". This search will retrieve documents about online encyclopedias that use the term "Internet" instead of "online." This increase in precision is very commonly counter-productive since it usually comes with a dramatic loss of recall. ^[2]
• Phrase search. A phrase search matches only those documents that contain a specified phrase, such as "Wikipedia, the free encyclopedia."
• Concordance search. A concordance search produces an alphabetical list of all principal words that occur in a text with their immediate context.
• Proximity search. A phrase search matches only those documents that contain two or more words that are separated by a specified number of words; a search for "Wikipedia" WITHIN2 "free" would retrieve only those documents in which the words "Wikipedia" and "free" occur within two words of each other.
• Regular expression. A regular expression employs a complex but powerful querying syntax that can be used to specify retrieval conditions with precision.
• Wildcard search. A search that substitutes one or more characters in a search query for a wildcard character such as an asterisk. For example, in the search function in Microsoft Word, using the asterisk in the search query "s*n" will find "sin", "son", "sun", etc. in a text.

Improved search algorithms

Technological advances have greatly improved the performance of free text searching. For example, Google's PageRank algorithm gives more prominence to documents to which other Web pages have linked. This algorithm dramatically improves users' perception of search precision, a fact that explains its popularity among Internet users. See search engine for additional examples.

Inverted index (Wikipedia)

Inverted index (Wikipedia)
Inverted index

An inverted index (also referred to as postings file or inverted file) is an index structure storing a mapping from words to their locations in a document or a set of documents, allowing full text search. It is the most popular data structure used in document retrieval systems.

There are two main variants of inverted indexes: A record level inverted index (or inverted file index) contains a list of references to documents for each word. A word level inverted index (or full inverted index) additionally contains the positions of each word within a document. The latter form offers more functionality (like phrase searches), but needs more time and space to be created.

1 Example 2 Applications 3 See also 4 References 5 External links

Example

Given the texts T₀ = "it is what it is", T₁ = "what is it" and T₂ = "it is a banana", we have the following inverted file index (where the integers in the set notation brackets refer to the subscripts of the text symbols, T₀, T₁ etc.):

"a":      {2}
"banana": {2}
"is":     {0, 1, 2}
"it":     {0, 1, 2}
"what":   {0, 1}

A term search for the terms "what", "is" and "it" would give the set .

With the same texts, we get the following full inverted index, where the pairs are document numbers and local word numbers. Like the document numbers, local word numbers also begin with zero. So, "banana": {(2, 3)} means the word "banana" is in the third document (T₂), and it is the fourth word in that document (position 3).

"a":      {(2, 2)}
"banana": {(2, 3)}
"is":     {(0, 1), (0, 4), (1, 1), (2, 1)}
"it":     {(0, 0), (0, 3), (1, 2), (2, 0)}
"what":   {(0, 2), (1, 0)}

If we run a phrase search for "what is it" we get hits for all the words in both document 0 and 1. But the terms occur only consecutively in document 1.

Applications

The inverted index data structure is a central component of a typical search engine indexing algorithm. A goal of a search engine implementation is to optimize the speed of the query: find the documents where word X occurs. Once a forward index is developed, which stores lists of words per document, it is next inverted to develop an inverted index. Querying the forward index would require sequential iteration through each document and to each word to verify a matching document. The time, memory, and processing resources to perform such a query are not always technically realistic. Instead of listing the words per document in the forward index, the inverted index data structure is developed which lists the documents per word.

With the inverted index created, the query can now be resolved by jumping to the word id (via random access) in the inverted index. Random access is generally regarded as being faster than sequential access.

See also

• Vector space model

References

• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 560–563 of section 6.5: Retrieval on Secondary Keys.
• Justin Zobel, Alistair Moffat and Kotagiri Ramamohanarao, Inverted files versus signature files for text indexing. ACM Transactions on Database Systems (TODS), Volume 23, Issue 4 (December 1998), Pages: 453 - 490.
• Justin Zobel and Alistair Moffat, Inverted Files for Text Search Engines . ACM Computing Surveys 38(2).

External links

• NIST's Dictionary of Algorithms and Data Structures: inverted index
• Managing Gigabytes for Java a free full-text search engine for large document collections written in Java.

Retrieved from "http://en.wikipedia.org/wiki/Inverted_index"

Categories: Data structures | Algorithms on strings

Implement Phonetic ("Sounds-like") Name Searches with Double Metaphone

Implement Phonetic ("Sounds-like") Name Searches with Double Metaphone Part VI: Other Methods & Additional Resources

• Download source files - 54 Kb


• Download demo projects - 470 Kb

Abstract

Simple information searches -- name lookups, word searches, etc. -- are often implemented in terms of an exact match criterion. However, given both the diversity of homophonic (pronounced the same) words and names, as well as the propensity for humans to misspell surnames, this simplistic criterion often yields less than desirable results, in the form of reduced result sets, missing records that differ by a misplaced letter or different national spelling.

This article series discusses Lawrence Phillips' Double Metaphone phonetic matching algorithm, and provides several useful implementations which can be employed in a variety of solutions to create more useful, effective searches of proper names in databases and other collections.

Introduction

This article series discusses the practical use of the Double Metaphone algorithm to phonetically search name data, using the author's implementations written for C++, COM (Visual Basic, etc.), scripting clients (VBScript, Jscript, ASP), SQL, and .NET (C#, VB.NET, and any other .NET language). For a discussion of the Double Metaphone algorithm itself, and Phillips' original code, see Phillips' article in the June 2000 CUJ, available here.

Part I introduces Double Metaphone and describes the author's C++ implementation and its use. Part II discusses the use of the author's COM implementation from within Visual Basic. Part III demonstrates use of the COM implementation from ASP and with VBScript. Part IV shows how to perform phonetic matching within SQL Server using the author's extended stored procedure. Part V demonstrates the author's .NET implementation. Finally, Part VI closes with a survey of phonetic matching alternatives, and pointers to other resources.

Double Metaphone limitations

While this article series has focused entirely on the Double Metaphone algorithm as a means to implement phonetic matching in one's applications, Double Metaphone bears some weaknesses that may render it unsuitable for a particular application, including:

• Though it works as a general-purpose phonetic search algorithm, Double Metaphone was designed for, and works best with, searching lists of proper names rather than large fields of generic text.


• Double Metaphone provides minimal ranking ability, apart from the three match levels described elsewhere in the series. This limits the ability to tune search results.


• Being a phonetic matching (vs. fuzzy matching like q-grams and edit distances) algorithm, Double Metaphone may fail to match misspelled words when the misspelling substantively alters the phonetic structure of a word.

Even bearing these limitations in mind, Double Metaphone is free, efficient, easy to use, and adaptable to a number of scenarios. Ultimately, only the designer of a particular system can decide if Double Metaphone is appropriate to his/her particular problem space.

Alternatives to Double Metaphone

Numerous other algorithms and techniques have been developed, each for different purposes, and each with varying efficacy. This section will explore some of the better-known techniques, and provide resources for more information on each method.

Soundex

Soundex was one of the first, if not the first, formalized phonetic matching algorithm. Soundex was developed for use by the US Census in the late 19^th century. Not surprisingly, this algorithm is remarkably simple, and woefully inadequate in most cases.

Nonetheless, one encounters Soundex in surprising places, even in modern software solutions. For example, Microsoft SQL Server offers a SOUNDEX function which, given a word, computes Soundex keys.

For more information on Soundex, a simple Internet search on "soundex" will likely yield fruitful results. Once again, the reader is encouraged to consider more advanced alternatives for any production system, as Soundex is both primitive and limited.

Metaphone

Double Metaphone is only the latest incarnation of the Metaphone algorithm, originally published by Lawrence Phillips in 1990. While arguably inferior to Double Metaphone, Metaphone does incorporate similar heuristics, and has the added advantage (and disadvantage) of producing only one phonetic key for a given word.

Phonix

Phonix is an improved version of Soundex, developed by T.N. Gadd and published in Association for Information Management's journal, Program [Gadd, T.N. `Fisching fore werds': phonetic retrieval of written text in information systems, 22(3) 1988, p. 222] and [Gadd, T.N. PHONIX: the algorithm, 24(4) 1990, p. 363]. While the articles are not available online, Phonix has been incorporated into a number of WAIS implementations, including freeWAIS, which is open-source and therefore freely available in source form.

The author has never experimented with Phonix, and therefore cannot write authoritatively regarding its performance; however being Soundex-based, it bears much of the same baggage which limits Soundex's performance. The paper by Zobel and Dart referenced at the end of this article performs some objective comparison of Phonix with several other algorithms, producing results which confirm this author's suspicions.

q-Gram based algorithms

A q-gram (sometimes called n-gram, primarily to confuse readers) in this context refers to a sequence of letters, q letters long, from a given word. For example, for q = 2, the word Nelson has the following q-grams:

NE EL LS SO ON

By comparison, Neilsen breaks down into these q-grams (q = 2):

NE EI IL LS SE EN

Clearly, Nelson and Neilsen share the NE and LS q-grams in common.

Various techniques have been developed which compare two words based on their q-grams. A simple example would be counting the number of q-grams two words have in common, with a higher count yielding a stronger match.

Technically, q-gram algorithms aren't strictly phonetic matching, in that they do not operate based on comparison of the phonetic characteristics of words. Instead, q-grams can be thought to compute the "distance", or amount of difference, between two words. Since phonetically similar words often have similar spellings, this technique can provide favorable results, yet it also successfully matches misspelled or otherwise mutated words, even if they are rendered phonetically disparate.

Edit distance based algorithms

Edit distance computes the "distance" between two words by counting the number of insert, replace, and delete operations required to permute one word into another. In general the fewer operations required, the closer the match. Some implementations assign varying scores to the insert, replace, and delete operations. Another common variation varies which operations are considered when computing the distance; for example, the replace operation may not be considered, thereby defining the edit distance solely in terms of insert and delete options.

One of the more popular algorithms in the edit distance class is Levenshtein distance (note the spelling; some references use the spelling 'Levenstein', which is technically incorrect).

As with q-gram algorithms, edit distance is not strictly phonetic, but often matches phonetically similar words due to similarities in spelling.

Proprietary algorithms

Several organizations offer data scrubbing, de-duplication, data normalizing, and merge-purge software, which implement some form of approximate text matching, albeit with varying degrees of success. The exact algorithms used are often proprietary, and seldom documented. The applicability of these systems to a particular problem must be carefully analyzed before adopting any one solution.

Other sources

The above list of alternative matching algorithms is far from complete, and provides only enough information to begin a search for suitable algorithms -- not to end one. This section lists other sources of information on phonetic matching, and approximate text matching, as well as links to additional Double Metaphone implementations.

Additional Double Metaphone implementations

• Links to several Metaphone and Double Metaphone implementations, including C, Perl, Java, and PHP.

Additional Phonetic Matching/Approximate text matching resources

• "Phonetic String Matching: Lessons from Information Retrieval" by Zobel and Dart. - A very readable paper comparing all of the matching techniques discussed in this article (except Metaphone and Double Metaphone, unfortunately), and a few more. Includes tables containing quantitative test results comparing various.


• "A Guided Tour to Approximate String Matching" by Gonzalo Navarro. - An excellent survey of approximate string matching, which is different from, but related to, phonetic matching.


• "Approximate Text Searching" by Gonzalo Navarro. - A very exhaustive discussion of approximate text matching issues. May be too technical for some readers. Note that the English version follows the Spanish text.


• "Searching Proper Names in Databases" by Pfeifer, Poersch, and Fuhr. - A very accessible discussion of several techniques specifically designed for searching databases of proper (last) names. Includes results of efficacy tests by the authors.


• "Learning String Edit Distance " by Ristad, and Yianilos. - Paper describing edit distance algorithms, and presenting an interesting stochastic model for learning an edit distance function from a set of examples. This latter subject is likely to be of limited interest to those seeking approximate string matching techniques, however the former topic is highly relevant.


• Richard Birkby's CodeProject article presenting four Soundex variations in C#. - Includes a brief discussion of Soundex performance.


• A very readable essay by Michael Gillel and describing the Levenshtein Distance algorithm, along with source code in VB, C++, and Java. Be sure to take note of the Resources section, which includes links to additional sites and implementations.


• "Finding String Distances", Dr Dobb's Journal, April 1992, by Ray Valdes. Interesting article discussing Levenshtein distance, and its applications not only to string matching but also to molecular biology, handwriting recognition, etc. Article available on DDJ archive CD. Source code available here.


• "A Comparison of String Distance Metrics for Name-Matching Tasks" by Cohen, Ravikumar, and Feinberg. - A nice, technical survey of techniques for measuring the "distance" between strings, for the purposes of matching proper names. Great source of additional information on edit distance techniques, including Levenshtein distance.


• SourceForge home for SecondString, a Java approximate string matching library by the authors of "A Comparison of String Distance Metrics for Name-Matching Tasks" referenced above. Includes, among other things, an implementation of Levenshtein distance.


• A powerfull full-text search engine implemented entirely in Java. - Includes Levenshtein distance code, along with all of the typical full text indexing features.


• AGREP - AGREP is a tool, similar to egrep, fgrep, and grep, which searches for a given pattern in files. AGREP uses an edit distance algorithm to perform approximate matching, making it of interest for experimenting with the results one can expect from such algorithms.

Conclusion

This article concludes the article series on phonetic matching of name data with Double Metaphone. In this article, some of the other major techniques for phonetic matching are presented, as well as links to additional resources for the reader interested in further research on the subject. By this point, the reader should understand that no one solution exists to the problem of matching similar but not identical text, and that candidate solutions should be selected based on the reader's specific criteria.

That said, hopefully this article series will lead the reader to strongly consider Double Metaphone, due to its ease of use, respectable performance, and readily available implementations in a variety of languages.

History

• 7-22-03 Initial publication


• 7-29-03 Added reference to Richard Birkby's Soundex article


• 7-31-03 Added hyperlinks between articles in the series


• 8-03-03 Added additional resources pertaining to the Levenshtein Distance algorithm

Article Series

• Implement Phonetic ("Sounds-like") Name Searches with Double Metaphone Part I: Introduction & C++ Implementation


• Implement Phonetic ("Sounds-like") Name Searches with Double Metaphone Part II: Visual Basic and Relational Database Solutions


• Implement Phonetic ("Sounds-like") Name Searches with Double Metaphone Part III: VBScript and ASP & Database Solutions


• Implement Phonetic ("Sounds-like") Name Searches with Double Metaphone Part IV: SQL Server and Advanced Database Topics


• Implement Phonetic ("Sounds-like") Name Searches with Double Metaphone Part V: .NET Implementation


• Implement Phonetic ("Sounds-like") Name Searches with Double Metaphone Part VI: Other Methods & Additional Resources

Technorati : Phonetic Search

Lawrence Philips' Metaphone Algorithm

Lawrence Philips' Metaphone Algorithm

Lawrence Philips' Metaphone Algorithm is an algorithm which returns the rough approximation of how an English word sounds. The author can be contacted at LFP at dolby com

A mailing list has been set up for the general discussion of the Metaphone algorithm. An archive for the mailing list can be found here

News

May 22, 2001
A PHP Implementation of the Double Metaphone Algorithm is now available.

August 8, 2000
A C and Perl Implementation of the Double Metaphone Algorithm is now available.

May 28, 2000
Added links to several other implementations of the original Metaphone algorithm.

May 27, 2000
There was a slight error in dmetaph-diff.txt (the list of exactly what words Aspell with the new Double Metaphone got and the original Aspell did not and vice versa) as the "Bad Spellers Mode" list was the same as the "Fast Mode." This is now fixed.

Original

The original Metaphone algorithm appeared in the December 1990 issue of Computer Language.

• Original Basic Code
• C Implementation by Michael Kuhn with several additional modifications of the algorithm by the author
• C Implementation by Sadru Fidai
• 4Gl Implementation
• C Implementation by Gary A. Parker, as part of the Snippets collection
• Perl & C Implementation by Michael G Schwern (The C library is also used by php4.)
• Java Implementation (must contact the author for binary and/or source)
• Active X Control (commerical)

Double

The double Metaphone algorithm is the new improved Metaphone algorithm.

• C/C++ Users Journal(tm) article
• Orignal Microsoft Visual C++ source code by Lawrence Philips
• Helper header file for those not using Microsoft Visual C++.
• A slightly modified version with has several bug fixes and gives back more than 4 characters. (diffs from the published version)
• Perl and C Implementation by Maurice Aubrey
• PHP Implementation by Stephen Woodbridge

The Metaphone Algorithm and Aspell

Even though, this site is hosted off of Aspell's site, it is not meant to be Aspell specific except for this section. Aspell is an Open Source Spell checker that does a superior job of coming up with suggestions. The magic behind my spell checker comes from merging Lawrence Philips excellent Metaphone algorithm and Ispell's near miss strategy which is inserting a space or hyphen, interchanging two adjacent letters, changing one letter, deleting a letter, or adding a letter. The current version of Aspell uses a modified version of the Metaphone algorithm in a tablized form.

To see if the Double Metaphone algorithm will lead to an improvement in suggestion strategy I substituted in it in place of the existing tablized code and was able to archive a 1% better score based on on some test data. However, for some words the new Metaphone algorithm lead to worse results. I plan on merging the new Double Metaphone algorithm into the exiting table, but will make sure that it always leads to better results by perhaps not adding some rules or adding a slight variation of the Double Metaphone rule.

---

kevina at users sourceforge net
This site is not officaly affiliated with Lawrence Philips in any way.