Python中的快速全文搜索算法

Python中的快速全文搜索算法有很多，其中最常用的是倒排索引算法和Trie树算法。以下将对这两种算法进行介绍，并给出使用例子。

1. 倒排索引算法：

倒排索引是一种常用的全文搜索算法，它通过构建一个词汇表和一个指向包含该词的文档的指针列表来实现快速搜索。倒排索引的主要思想是将文档集合中的每个文档拆分成词语的序列，然后对每个词语进行索引。

下面是一个简单的使用倒排索引算法实现全文搜索的例子：

class InvertedIndex:
    def __init__(self):
        self.index = {}

    def add_document(self, doc_id, text):
        words = text.split()
        for word in words:
            if word in self.index:
                self.index[word].append(doc_id)
            else:
                self.index[word] = [doc_id]

    def search(self, query):
        words = query.split()
        result = set(self.index.get(words[0], []))
        for word in words[1:]:
            result.intersection_update(self.index.get(word, []))
        return result

# 创建倒排索引对象
index = InvertedIndex()

# 添加文档
index.add_document(1, "python is a programming language")
index.add_document(2, "python is popular")

# 搜索文档
result = index.search("python language")
print(result)  # 输出：{1}

2. Trie树算法：

Trie树，也称为字典树或前缀树，是一种用于快速搜索的数据结构，它能够在O(m)的时间复杂度下查找字符串，其中m是字符串的长度。

下面是一个简单的使用Trie树算法实现全文搜索的例子：

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, query):
        node = self.root
        for char in query:
            if char not in node.children:
                return []
            node = node.children[char]
        return self._get_words(node, query)

    def _get_words(self, node, prefix):
        words = []
        if node.is_end_of_word:
            words.append(prefix)
        for char, child in node.children.items():
            words.extend(self._get_words(child, prefix + char))
        return words

# 创建Trie对象
trie = Trie()

# 插入单词
trie.insert("python")
trie.insert("programming")
trie.insert("language")

# 搜索单词
result = trie.search("py")
print(result)  # 输出：['python']

以上是两种常用的快速全文搜索算法的示例，分别基于倒排索引和Trie树实现。根据实际需求选择适合的算法可以提高搜索性能和效率。