Skip to main content

synapse_search/
lib.rs

1//! # synapse-search
2//!
3//! A blazing-fast, embeddable, in-memory fuzzy search and autocomplete engine.
4//!
5//! ## Features
6//! - **Prefix autocomplete** via a compressed Trie
7//! - **Typo-tolerant fuzzy search** via Levenshtein distance
8//! - **Relevance-ranked full-text search** via TF-IDF inverted index
9//!
10//! ## Example
11//! ```rust
12//! use synapse_search::SynapseSearch;
13//!
14//! let mut engine = SynapseSearch::new();
15//! engine.add(1, "iPhone 15 Pro Max");
16//! engine.add(2, "Samsung Galaxy S24");
17//! engine.add(3, "Google Pixel 9 Pro");
18//!
19//! // Exact prefix autocomplete
20//! let suggestions = engine.autocomplete("iph", 5);
21//! // -> ["iphone"]
22//!
23//! // Typo-tolerant fuzzy search
24//! let results = engine.fuzzy_search("iphne", 2, 10);
25//! // -> [(1, "iPhone 15 Pro Max")]
26//!
27//! // Full-text ranked search
28//! let results = engine.search("pro", 10);
29//! // -> [(1, ...), (3, ...)]  — both contain "pro"
30//! ```
31
32pub mod trie;
33pub mod lev;
34pub mod index;
35
36use trie::Trie;
37use index::{InvertedIndex, Document};
38use lev::fuzzy_match;
39
40/// The unified search engine combining autocomplete, fuzzy matching, and full-text search.
41pub struct SynapseSearch {
42    trie: Trie,
43    index: InvertedIndex,
44    next_id: u64,
45}
46
47impl SynapseSearch {
48    /// Create a new empty search engine.
49    pub fn new() -> Self {
50        Self {
51            trie: Trie::new(),
52            index: InvertedIndex::new(),
53            next_id: 0,
54        }
55    }
56
57    /// Add a document with an explicit ID.
58    pub fn add(&mut self, id: u64, text: &str) {
59        // Index each word in the trie for autocomplete
60        let tokens = index::tokenize(text);
61        for token in &tokens {
62            self.trie.insert(token);
63        }
64
65        // Index the full document for ranked search
66        self.index.add(Document {
67            id,
68            text: text.to_string(),
69        });
70
71        if id >= self.next_id {
72            self.next_id = id + 1;
73        }
74    }
75
76    /// Add a document with an auto-generated ID. Returns the assigned ID.
77    pub fn add_auto(&mut self, text: &str) -> u64 {
78        let id = self.next_id;
79        self.add(id, text);
80        id
81    }
82
83    /// Get prefix-based autocomplete suggestions.
84    /// Returns matching tokens (lowercased words), up to `limit`.
85    pub fn autocomplete(&self, prefix: &str, limit: usize) -> Vec<String> {
86        self.trie.autocomplete(prefix, limit)
87    }
88
89    /// Perform typo-tolerant fuzzy search across all indexed tokens.
90    /// Returns (doc_id, document_text) pairs for documents containing
91    /// any token within `max_distance` edits of the query.
92    pub fn fuzzy_search(&self, query: &str, max_distance: usize, limit: usize) -> Vec<(u64, String)> {
93        // Find fuzzy-matched tokens
94        let matches = fuzzy_match(query, &self.index.all_tokens, max_distance);
95
96        if matches.is_empty() {
97            return Vec::new();
98        }
99
100        // Search for documents containing any matched token, collect unique doc IDs
101        let mut seen = std::collections::HashSet::new();
102        let mut results = Vec::new();
103
104        for (matched_token, _distance) in &matches {
105            let search_results = self.index.search(matched_token, limit);
106            for (doc_id, _score) in search_results {
107                if seen.insert(doc_id) {
108                    if let Some(text) = self.index.documents.get(&doc_id) {
109                        results.push((doc_id, text.clone()));
110                    }
111                }
112                if results.len() >= limit {
113                    return results;
114                }
115            }
116        }
117
118        results
119    }
120
121    /// Perform full-text ranked search using TF-IDF scoring.
122    /// Returns (doc_id, score) pairs sorted by relevance.
123    pub fn search(&self, query: &str, limit: usize) -> Vec<(u64, f64)> {
124        self.index.search(query, limit)
125    }
126
127    /// Get the original text of a document by ID.
128    pub fn get_document(&self, id: u64) -> Option<&String> {
129        self.index.documents.get(&id)
130    }
131
132    /// Total number of indexed documents.
133    pub fn doc_count(&self) -> u64 {
134        self.index.doc_count
135    }
136}
137
138#[cfg(test)]
139mod tests {
140    use super::*;
141
142    #[test]
143    fn test_full_engine() {
144        let mut engine = SynapseSearch::new();
145        engine.add(1, "iPhone 15 Pro Max");
146        engine.add(2, "Samsung Galaxy S24 Ultra");
147        engine.add(3, "Google Pixel 9 Pro");
148        engine.add(4, "OnePlus 12");
149
150        // Autocomplete
151        let suggestions = engine.autocomplete("iph", 5);
152        assert!(suggestions.contains(&"iphone".to_string()));
153
154        let suggestions = engine.autocomplete("sam", 5);
155        assert!(suggestions.contains(&"samsung".to_string()));
156
157        // Fuzzy search with typo
158        let results = engine.fuzzy_search("iphne", 2, 10);
159        assert!(!results.is_empty());
160        assert_eq!(results[0].0, 1); // iPhone doc
161
162        let results = engine.fuzzy_search("samung", 2, 10);
163        assert!(!results.is_empty());
164        assert_eq!(results[0].0, 2); // Samsung doc
165
166        // Full-text search
167        let results = engine.search("pro", 10);
168        let ids: Vec<u64> = results.iter().map(|r| r.0).collect();
169        assert!(ids.contains(&1)); // iPhone 15 Pro Max
170        assert!(ids.contains(&3)); // Google Pixel 9 Pro
171        assert!(!ids.contains(&2)); // Samsung doesn't have "pro"
172
173        assert_eq!(engine.doc_count(), 4);
174    }
175}