Building A Python-based Search Engine

PyCon 2012 talk - A talk introducing the fundamentals of search engines via a small pure Python library.

1. Building A Python-Based Search Engine
2. Who Am I? • Daniel Lindsley
3. Who Am I? • Daniel Lindsley • From Lawrence, KS
4. Not This Kansas
5. This Lawrence, Kansas
6. This Lawrence, Kansas
7. This Lawrence, Kansas
8. This Lawrence, Kansas
9. This Lawrence, Kansas
10. This Lawrence, Kansas
11. This Lawrence, Kansas
12. But Really...
14. Who Am I? • Daniel Lindsley • From Lawrence, KS • I run Toast Driven
15. Toast Driven
16. Who Am I? • Daniel Lindsley • From Lawrence, KS • I run Toast Driven • Consulting & Open Source
17. Who Am I? • Daniel Lindsley • From Lawrence, KS • I run Toast Driven • Consulting & Open Source • Primary author of Haystack
19. Who Am I? • Daniel Lindsley • From Lawrence, KS • I run Toast Driven • Consulting & Open Source • Primary author of Haystack • Adds pluggable search to Django
20. The Goal
21. The Goal • Teach you how search works
22. The Goal • Teach you how search works • Increase your comfort with other engines
23. The Goal • Teach you how search works • Increase your comfort with other engines • NOT to develop yet another engine
24. Why Care About Search?
25. Why Care About Search? “Doesn’t the handle that?”
26. Why In-House Search? • Standard crawlers have to scrape HTML
27. Why In-House Search? • Standard crawlers have to scrape HTML • You know the data model better than they do
28. Why In-House Search? • Standard crawlers have to scrape HTML • You know the data model better than they do • Maybe it’s not a web app at all!
29. Core Concepts
30. Core Concepts • Document-based
31. Core Concepts • Document-based • NEVER just looking through a string
32. Core Concepts • Document-based • NEVER just looking through a string • Inverted Index
33. Core Concepts • Document-based • NEVER just looking through a string • Inverted Index • Stemming
34. Core Concepts • Document-based • NEVER just looking through a string • Inverted Index • Stemming • N-gram
35. Core Concepts • Document-based • NEVER just looking through a string • Inverted Index • Stemming • N-gram • Relevance
36. Terminology
37. Terminology • Engine • Document • Corpus • Stopword • Stemming • Position • Segments • Relevance • Faceting • Boost
38. Engine
40. Engine The black box you hand a query to & get results from.
41. Document
43. Document A text blob with optional metadata.
44. Corpus
46. Corpus The collection of all documents.
47. Stopword
49. Stopword A short word that doesn’t contribute to relevance & is typically ignored. “and”, “a”, “the”, “but”, etc.
50. Stemming
52. Stemming Finding the root of a word.
53. Segments
55. Segments Sharded data storing the inverted index.
56. Relevance
58. Relevance The algorithm(s) used to rank the results based on the query.
59. Faceting
61. Faceting Providing counts of results within the results that match certain criteria. “Drill-down”
62. Boost
64. Boost Artificially enhancing the relevance of certain documents based on a condition.
65. This concludes the Funny Cat Pictures portion of this presentation. Please remain seated and calm.
67. Indexing
68. Indexing • Four Main Components • Receiving/Storing Documents
69. Indexing • Four Main Components • Receiving/Storing Documents • Tokenization
70. Indexing • Four Main Components • Receiving/Storing Documents • Tokenization • Generating Terms
71. Indexing • Four Main Components • Receiving/Storing Documents • Tokenization • Generating Terms • Indexing the Terms
72. Documents
73. Documents • NOT a row in the DB
74. Documents • NOT a row in the DB • Think blob of text + metadata
75. Documents • NOT a row in the DB • Think blob of text + metadata • Text quality is THE most important thing!
76. Documents • NOT a row in the DB • Think blob of text + metadata • Text quality is THE most important thing! • Flat, NOT relational!
77. Documents • NOT a row in the DB • Think blob of text + metadata • Text quality is THE most important thing! • Flat, NOT relational! • Denormalize, denormalize, denormalize!
78. Documents
79. Tokenization
80. Tokenization • Using the text blob, you: • Split on whitespace
81. Tokenization • Using the text blob, you: • Split on whitespace • Lowercase
82. Tokenization • Using the text blob, you: • Split on whitespace • Lowercase • Filter out stopwords
83. Tokenization • Using the text blob, you: • Split on whitespace • Lowercase • Filter out stopwords • Strip punctuation
84. Tokenization • Using the text blob, you: • Split on whitespace • Lowercase • Filter out stopwords • Strip punctuation • Etc.
85. The point is to Normalize the tokens. Consistent little atomic units we can assign meaning to & work with.
86. Stemming
87. Stemming • To avoid manually searching through the whole blob, you tokenize
88. Stemming • To avoid manually searching through the whole blob, you tokenize • More post-processing
89. Stemming • To avoid manually searching through the whole blob, you tokenize • More post-processing • THEN! you find the root word
90. Stemming (cont.) • Examples: • “testing” ➙ “test” • “searchers” ➙ “searcher” ➙ “search”
91. Stemming (cont.) • These become the terms in the inverted index
92. Stemming (cont.) • These become the terms in the inverted index • When you do the same to the query, you can match them up
93. Stemming (cont.) • Cons: • Stemming only works well if you know the grammatical structure of the language
94. Stemming (cont.) • Cons: • Stemming only works well if you know the grammatical structure of the language • Most are specific to English, though other stemmers available
95. Stemming (cont.) • Cons: • Stemming only works well if you know the grammatical structure of the language • Most are specific to English, though other stemmers available • Hard to make work cross-language
97. How Do We Solve This Shortcoming? Let’s generate the terms from a different angle...
98. N-grams
99. N-grams • Solves some of the shortcomings of stemming with new tradeoffs
100. N-grams • Solves some of the shortcomings of stemming with new tradeoffs • Passes a "window" over the tokenized data
101. N-grams • Solves some of the shortcomings of stemming with new tradeoffs • Passes a "window" over the tokenized data • These windows of data become the terms in the index
102. N-grams (cont.) • Examples (gram size of 3): • hello world • [‘hel’]
103. N-grams (cont.) • Examples (gram size of 3): • hello world • [‘hel’, ‘ell’]
104. N-grams (cont.) • Examples (gram size of 3): • hello world • [‘hel’, ‘ell’, ‘llo’]
105. N-grams (cont.) • Examples (gram size of 3): • hello world • [‘hel’, ‘ell’, ‘llo’, ‘wor’]
106. N-grams (cont.) • Examples (gram size of 3): • hello world • [‘hel’, ‘ell’, ‘llo’, ‘wor’, ‘orl’]
107. N-grams (cont.) • Examples (gram size of 3): • hello world • [‘hel’, ‘ell’, ‘llo’, ‘wor’, ‘orl’, ‘rld’]
108. Edge N-grams (cont.) • Typically used with multiple gram sizes • Examples (gram size of 3 to 6): • hello world • [‘hel’]
109. Edge N-grams (cont.) • Typically used with multiple gram sizes • Examples (gram size of 3 to 6): • hello world • [‘hel’, ‘hell’]
110. Edge N-grams (cont.) • Typically used with multiple gram sizes • Examples (gram size of 3 to 6): • hello world • [‘hel’, ‘hell’, ‘hello’]
111. Edge N-grams (cont.) • Typically used with multiple gram sizes • Examples (gram size of 3 to 6): • hello world • [‘hel’, ‘hell’, ‘hello’, ‘wor’]
112. Edge N-grams (cont.) • Typically used with multiple gram sizes • Examples (gram size of 3 to 6): • hello world • [‘hel’, ‘hell’, ‘hello’, ‘wor’, ‘worl’]
113. Edge N-grams (cont.) • Typically used with multiple gram sizes • Examples (gram size of 3 to 6): • hello world • [‘hel’, ‘hell’, ‘hello’, ‘wor’, ‘worl’, ‘world’]
114. N-grams (cont.) • Pros: • Great for autocomplete (matches small fragments quickly)
115. N-grams (cont.) • Pros: • Great for autocomplete (matches small fragments quickly) • Works across languages (even Asian!)
116. N-grams (cont.) • Cons: • Lots more terms in the index
117. N-grams (cont.) • Cons: • Lots more terms in the index • Initial quality can suffer little
118. N-grams (cont.)
119. Inverted Index
120. Inverted Index • The heart of the engine
121. Inverted Index • The heart of the engine • Like a dictionary
122. Inverted Index • The heart of the engine • Like a dictionary • Keys matter (terms from all docs)
123. Inverted Index • The heart of the engine • Like a dictionary • Keys matter (terms from all docs) • Stores position & document IDs
124. Inverted Index
125. Segments
126. Segments • Lots of different ways to do this
127. Segments • Lots of different ways to do this • Many follow Lucene
128. Segments • Lots of different ways to do this • Many follow Lucene • We’re going to cheat & take a slightly simpler approach...
129. Segments • Flat files
130. Segments • Flat files • Hashed keys
131. Segments • Flat files • Hashed keys • Always sorted
132. Segments • Flat files • Hashed keys • Always sorted • Use JSON for the position/document data
133. Segments
134. Searching
135. Searching • Three Main Components • Query Parser
136. Searching • Three Main Components • Query Parser • Index Reader
137. Searching • Three Main Components • Query Parser • Index Reader • Scoring (Relevance)
138. Query Parser
139. Query Parser • Parse out the structure
140. Query Parser • Parse out the structure • Process the elements the same way you prepared the document
141. Query Parser
142. Index Reader
143. Index Reader • Per-term, hash the term to get the right file
144. Index Reader • Per-term, hash the term to get the right file • Rip through & collect all the results of positions/documents
145. Index Reader
146. Scoring
147. Scoring • Reorder the collection of documents based on how well each fits the query
148. Scoring • Reorder the collection of documents based on how well each fits the query • Lots of choices • BM25
149. Scoring • Reorder the collection of documents based on how well each fits the query • Lots of choices • BM25 • Phased
150. Scoring • Reorder the collection of documents based on how well each fits the query • Lots of choices • BM25 • Phased • Google’s PageRank
151. Scoring
153. Demo-time!
155. Advanced Topics Here be dragons...
156. Faceting
157. Faceting • For a given field, collect all terms
158. Faceting • For a given field, collect all terms • Count the length of the unique document ids for each
159. Faceting • For a given field, collect all terms • Count the length of the unique document ids for each • Order by descending count
160. Boost
161. Boost • During the scoring process • If a condition is met, alter the score accordingly
162. More Like This
163. More Like This • Collect all the terms for a given document
164. More Like This • Collect all the terms for a given document • Sort based on how many times a document is seen in the set
165. More Like This • Collect all the terms for a given document • Sort based on how many times a document is seen in the set • This is a simplistic view
166. More Like This • Collect all the terms for a given document • Sort based on how many times a document is seen in the set • This is a simplistic view • More complete solutions use NLP to increase quality
167. microsearch https://github.com/toastdriven/microsearch A complete version of everything presented here.
168. Additional Resources • http://nlp.stanford.edu/IR-book/ • http://shop.oreilly.com/product/9780596529321.do • http://wiki.apache.org/solr/AnalyzersTokenizersTokenFilters • http://lucene.apache.org/core/old_versioned_docs/versions/ 3_0_0/fileformats.html • http://www.sqlite.org/wal.html • http://snowball.tartarus.org/ • http://sphinxsearch.com/blog/2010/08/17/how-sphinx- relevance-ranking-works/
169. Thanks!
170. Photo Credits: http://www.google.com/ http://www.flickr.com/photos/iko/145211107/ http://www.flickr.com/photos/tupwanders/79473424/ http://www.flickr.com/photos/tusnelda/6140792529/ http://www.flickr.com/photos/tooled/2178272773/ http://www.flickr.com/photos/jurvetson/156830367/ http://www.flickr.com/photos/23258385@N04/2235793476/ http://www.flickr.com/photos/scjn/3450910519/ http://www.flickr.com/photos/freefoto/3161020418/ http://www.flickr.com/photos/russelldavies/375432858/ http://www.flickr.com/photos/paul_lowry/2266388742/
171. Photo Credits: http://www.thefunnyblog.org/2011/06/07/this-is-relevant-to-my-interests/ http://animalcapshunz.icanhascheezburger.com/2011/12/14/funny-captions-dont-worry-were-from-the-internet/ http://www.flickr.com/photos/63916082@N00/224205907/ http://www.flickr.com/photos/neal1960/2676990168/ http://www.flickr.com/photos/ksjaycat/6816890165 http://www.flickr.com/photos/jcroft/331535213/ http://www.flickr.com/photos/historian77/409548647/ http://www.flickr.com/photos/marketmedia/3748493050/ http://www.flickr.com/photos/mytravelphotos/4624744750/in/set-72157624101448770/ http://www.flickr.com/photos/ubernostrum/2262907665/
172. I’m Daniel Lindsley of Toast Driven @toastdriven http://toastdriven.com/