Introduction

Simple Full-Text search engine with no external dependencies written in C#.

The aim of this project is to showcase algorithms, data structures and techniques that are used to create full-text search engines.

Source Repository

Query Language

• WORD(apple) - single word
• WILD(app*) - wildcard pattern
• EDIT(apple, 1) - Levenshtein (edit distance, fuzzy search)

Conjunction operators

• OR - boolean or
• AND - boolean and
• SEQ - sequence of words, phrase

Examples of queries:

• AND(WORD(apple), OR(WILD(a*), EDIT(apple, 1)))
• SEQ(WORD(hello), WORD(world))

Data Structures

• Dictionary of the persistent index is implemented using:
  • Ternary Search Tree.
  • Finite State Transducer (FST).
• Key-value storage for document metadata is based on persistent B-Tree implementation: B-Tree
• Packed Integers.
• Classic data structures:
  • Heap
  • Linked List
  • LFU and LRU Cache

Algorithms

• Approximate term matching is based on Levenshtein automaton.
• Query Language parser is implemented using recursive descent parser technique.
• A method for encoding/decoding occurrences uses:
  • Group VarInt encoding.
  • Delta encoding.
  • VarInt encoding.
• Classic algorithms:
  • Binary search
  • Heap sort
  • Huffman Encoding

References

• Introduction to Information Retrieval

  

• Compilers: Principles, Techniques, and Tools

  

• Information Retrieval: Implementing and Evaluating Search Engines