为什么需要自己构建搜索引擎?
- Published on
为什么要自己构建?
我知道你在想什么。"为什么不用 Elasticsearch?"或者"Algolia 怎么样?"这些都是不错的选择,但它们带来了复杂性。你需要学习它们的 API,管理它们的基础设施,还要处理它们的各种怪癖。
有时候,你只需要一个能:
- 与现有数据库协同工作的工具
- 不需要外部服务的解决方案
- 易于理解和调试的系统
- 真正能找到相关结果的引擎
这就是我构建的东西。一个使用你现有数据库的搜索引擎,它尊重你当前的架构,让你完全控制它的工作方式。
核心思想
概念很简单:对所有内容进行分词,存储它们,然后在搜索时匹配分词。
工作原理如下:
- 索引:当你添加或更新内容时,我们将其拆分为分词(单词、前缀、n-gram),并将它们与权重一起存储
- 搜索:当有人搜索时,我们用同样的方式对他们的查询进行分词,找到匹配的分词,并对结果进行评分
- 评分:我们使用存储的权重来计算相关性分数
魔法之处在于分词和加权。让我给你展示具体如何实现。
构建模块 1:数据库结构
我们需要两个简单的表:index_tokens 和 index_entries。
index_tokens
这个表存储所有唯一的分词及其分词器权重。每个分词名称可以有多个具有不同权重的记录——每种分词器一个。
// index_tokens 表结构
id | name | weight
---|---------|-------
1 | parser | 20 // 来自 WordTokenizer
2 | parser | 5 // 来自 PrefixTokenizer
3 | parser | 1 // 来自 NGramsTokenizer
4 | parser | 10 // 来自 SingularTokenizer
为什么按权重分别存储分词?不同的分词器会以不同的权重产生相同的分词。例如,来自 WordTokenizer 的 "parser" 权重为 20,但来自 PrefixTokenizer 的 "parser" 权重为 5。我们需要单独的记录来正确计算匹配分数。
唯一约束是 (name, weight),所以相同的分词名称可以以不同的权重存在多次。
index_entries
这个表将分词链接到文档,并带有字段特定的权重。
// index_entries 表结构
id | token_id | document_type | field_id | document_id | weight
---|----------|---------------|----------|-------------|-------
1 | 1 | 1 | 1 | 42 | 2000
2 | 2 | 1 | 1 | 42 | 500
这里的权重是最终计算的权重:field_weight × tokenizer_weight × ceil(sqrt(token_length))。这编码了评分所需的所有信息。我们将在文章后面讨论评分。
我们在以下字段上添加索引:
- (document_type, document_id) - 用于快速文档查找
- token_id - 用于快速分词查找
- (document_type, field_id) - 用于字段特定查询
- weight - 用于按权重过滤
为什么是这个结构?简单、高效,并且充分利用了数据库的优势。
构建模块 2:分词
什么是分词?它是将文本分解为可搜索片段的过程。"parser" 这个词会根据使用的分词器变成 ["parser"]、["par", "pars", "parse", "parser"] 或 ["par", "ars", "rse", "ser"] 等分词。
为什么需要多个分词器?不同的策略满足不同的匹配需求。一个用于精确匹配,另一个用于部分匹配,还有一个用于拼写错误。
所有分词器都实现一个简单的接口:
interface TokenizerInterface
{
public function tokenize(string $text): array; // 返回 Token 对象数组
public function getWeight(): int; // 返回分词器权重
}
简单的契约,易于扩展。
单词分词器
这个很简单——它将文本拆分为单个单词。"parser" 就变成 ["parser"]。简单,但对精确匹配很强大。
首先,我们规范化文本。全部小写,移除特殊字符,规范化空格:
class WordTokenizer implements TokenizerInterface
{
public function tokenize(string $text): array
{
// 规范化:小写,移除特殊字符
$text = mb_strtolower(trim($text));
$text = preg_replace('/[^a-z0-9]/', ' ', $text);
$text = preg_replace('/\s+/', ' ', $text);
接下来,我们拆分成单词并过滤掉短的:
// 拆分成单词,过滤短的
$words = explode(' ', $text);
$words = array_filter($words, fn($w) => mb_strlen($w) >= 2);
为什么要过滤短单词?单字符单词通常太常见,没有用。"a"、"I"、"x" 对搜索没有帮助。
最后,我们将唯一的单词作为 Token 对象返回:
// 返回带权重的 Token 对象
return array_map(
fn($word) => new Token($word, $this->weight),
array_unique($words)
);
}
}
权重:20(精确匹配的高优先级)
前缀分词器
这生成单词前缀。"parser" 变成 ["par", "pars", "parse", "parser"](最小长度为 4)。这有助于部分匹配和类似自动完成的行为。
首先,我们提取单词(与 WordTokenizer 相同的规范化):
class PrefixTokenizer implements TokenizerInterface
{
public function __construct(
private int $minPrefixLength = 4,
private int $weight = 5
) {}
public function tokenize(string $text): array
{
// 与 WordTokenizer 相同的规范化
$words = $this->extractWords($text);
然后,对每个单词,我们生成从最小长度到完整单词的前缀:
$tokens = [];
foreach ($words as $word) {
$wordLength = mb_strlen($word);
// 从最小长度到完整单词生成前缀
for ($i = $this->minPrefixLength; $i <= $wordLength; $i++) {
$prefix = mb_substr($word, 0, $i);
$tokens[$prefix] = true; // 使用关联数组确保唯一性
}
}
为什么使用关联数组?它确保唯一性。如果 "parser" 在文本中出现两次,我们只需要一个 "parser" 分词。
最后,我们将键转换为 Token 对象:
return array_map(
fn($prefix) => new Token($prefix, $this->weight),
array_keys($tokens)
);
}
}
权重:5(中等优先级)
为什么要设置最小长度?避免太多小的分词。短于 4 个字符的前缀通常太常见,没有用。
N-Gram 分词器
这创建固定长度的字符序列(我使用 3)。"parser" 变成 ["par", "ars", "rse", "ser"]。这可以捕获拼写错误和部分单词匹配。
首先,我们提取单词:
class NGramsTokenizer implements TokenizerInterface
{
public function __construct(
private int $ngramLength = 3,
private int $weight = 1
) {}
public function tokenize(string $text): array
{
$words = $this->extractWords($text);
然后,对每个单词,我们在上面滑动一个固定长度的窗口:
$tokens = [];
foreach ($words as $word) {
$wordLength = mb_strlen($word);
// 固定长度的滑动窗口
for ($i = 0; $i <= $wordLength - $this->ngramLength; $i++) {
$ngram = mb_substr($word, $i, $this->ngramLength);
$tokens[$ngram] = true;
}
}
滑动窗口:对于长度为 3 的 "parser",我们得到:
- 位置 0:"par"
- 位置 1:"ars"
- 位置 2:"rse"
- 位置 3:"ser"
为什么这有效?即使有人输入 "parsr"(拼写错误),我们仍然得到 "par" 和 "ars" 分词,它们与正确拼写的 "parser" 匹配。
最后,我们转换为 Token 对象:
return array_map(
fn($ngram) => new Token($ngram, $this->weight),
array_keys($tokens)
);
}
}
权重:1(低优先级,但捕获边缘情况)
为什么是 3?在覆盖范围和噪音之间取得平衡。太短你会得到太多匹配,太长你会错过拼写错误。
规范化
所有分词器都进行相同的规范化:
- 全部小写
- 移除特殊字符(只保留字母数字)
- 规范化空格(多个空格变为单个空格)
这确保无论输入格式如何都能一致匹配。
构建模块 3:权重系统
我们有三个层次的权重协同工作:
- 字段权重:标题 vs 内容 vs 关键词
- 分词器权重:单词 vs 前缀 vs n-gram(存储在 index_tokens 中)
- 文档权重:存储在 index_entries 中(计算:field_weight × tokenizer_weight × ceil(sqrt(token_length)))
最终权重计算
索引时,我们这样计算最终权重:
$finalWeight = $fieldWeight * $tokenizerWeight * ceil(sqrt($tokenLength));
例如:
- 标题字段:权重 10
- 单词分词器:权重 20
- 分词 "parser":长度 6
- 最终权重:10 × 20 × ceil(sqrt(6)) = 10 × 20 × 3 = 600
为什么要使用 ceil(sqrt())?较长的分词更具体,但我们不希望权重随着很长的分词而爆炸性增长。"parser" 比 "par" 更具体,但 100 个字符的分词不应该有 100 倍的权重。平方根函数给我们递减的回报——较长的分词仍然得分更高,但不是线性的。我们使用 ceil() 向上取整到最近的整数,保持权重为整数。
调整权重
你可以为你的用例调整权重:
- 如果标题最重要,增加标题字段的权重
- 如果你想优先考虑精确匹配,增加分词器的权重
- 如果你希望较长分词更重要或更不重要,调整分词长度函数(ceil(sqrt)、log 或线性)
你可以确切地看到权重是如何计算的,并根据需要进行调整。
构建模块 4:索引服务
索引服务接收一个文档并将其所有分词存储在数据库中。
接口
可以索引的文档实现 IndexableDocumentInterface:
interface IndexableDocumentInterface
{
public function getDocumentId(): int;
public function getDocumentType(): DocumentType;
public function getIndexableFields(): IndexableFields;
}
要让文档可搜索,你需要实现这三个方法:
class Post implements IndexableDocumentInterface
{
public function getDocumentId(): int
{
return $this->id ?? 0;
}
public function getDocumentType(): DocumentType
{
return DocumentType::POST;
}
public function getIndexableFields(): IndexableFields
{
$fields = IndexableFields::create()
->addField(FieldId::TITLE, $this->title ?? '', 10)
->addField(FieldId::CONTENT, $this->content ?? '', 1);
// 如果有关键词则添加
if (!empty($this->keywords)) {
$fields->addField(FieldId::KEYWORDS, $this->keywords, 20);
}
return $fields;
}
}
三个要实现的方法:
getDocumentType():返回文档类型枚举getDocumentId():返回文档 IDgetIndexableFields():使用流式 API 构建带权重的字段
你可以通过以下方式索引文档:
- 创建/更新时(通过事件监听器)
- 通过命令:
app:index-document、app:reindex-documents - 通过 cron(用于批量重新索引)
工作原理
这是索引过程的逐步说明。
首先,我们获取文档信息:
class SearchIndexingService
{
public function indexDocument(IndexableDocumentInterface $document): void
{
// 1. 获取文档信息
$documentType = $document->getDocumentType();
$documentId = $document->getDocumentId();
$indexableFields = $document->getIndexableFields();
$fields = $indexableFields->getFields();
$weights = $indexableFields->getWeights();
文档通过 IndexableFields 构建器提供其字段和权重。
接下来,我们移除这个文档的现有索引。这处理更新——如果文档改变了,我们需要重新索引它:
// 2. 移除这个文档的现有索引
$this->removeDocumentIndex($documentType, $documentId);
// 3. 准备批量插入数据
$insertData = [];
为什么要先移除?如果我们只是添加新的分词,我们会有重复项。最好重新开始。
现在,我们处理每个字段。对每个字段,我们运行所有分词器:
// 4. 处理每个字段
foreach ($fields as $fieldIdValue => $content) {
if (empty($content)) {
continue;
}
$fieldId = FieldId::from($fieldIdValue);
$fieldWeight = $weights[$fieldIdValue] ?? 0;
// 5. 在这个字段上运行所有分词器
foreach ($this->tokenizers as $tokenizer) {
$tokens = $tokenizer->tokenize($content);
对每个分词器,我们得到分词。然后,对每个分词,我们在数据库中查找或创建它并计算最终权重:
foreach ($tokens as $token) {
$tokenValue = $token->value;
$tokenWeight = $token->weight;
// 6. 在 index_tokens 中查找或创建分词
$tokenId = $this->findOrCreateToken($tokenValue, $tokenWeight);
// 7. 计算最终权重
$tokenLength = mb_strlen($tokenValue);
$finalWeight = (int) ($fieldWeight * $tokenWeight * ceil(sqrt($tokenLength)));
// 8. 添加到批量插入
$insertData[] = [
'token_id' => $tokenId,
'document_type' => $documentType->value,
'field_id' => $fieldId->value,
'document_id' => $documentId,
'weight' => $finalWeight,
];
}
}
}
为什么要批量插入?性能。与其一次插入一行,我们收集所有行并在一个查询中插入它们。
最后,我们批量插入所有内容:
// 9. 批量插入以提高性能
if (!empty($insertData)) {
$this->batchInsertSearchDocuments($insertData);
}
}
findOrCreateToken 方法很简单:
private function findOrCreateToken(string $name, int $weight): int
{
// 尝试查找具有相同名称和权重的现有分词
$sql = "SELECT id FROM index_tokens WHERE name = ? AND weight = ?";
$result = $this->connection->executeQuery($sql, [$name, $weight])->fetchAssociative();
if ($result) {
return (int) $result['id'];
}
// 创建新分词
$insertSql = "INSERT INTO index_tokens (name, weight) VALUES (?, ?)";
$this->connection->executeStatement($insertSql, [$name, $weight]);
return (int) $this->connection->lastInsertId();
}
}
为什么要查找或创建?分词在文档之间共享。如果权重为 20 的 "parser" 已经存在,我们就重用它。不需要创建重复项。
关键点:
- 我们先移除旧索引(处理更新)
- 我们批量插入以提高性能(一个查询而不是多个)
- 我们查找或创建分词(避免重复)
- 我们动态计算最终权重
构建模块 5:搜索服务
搜索服务接收查询字符串并找到相关文档。它使用与索引文档时相同的分词器对查询进行分词,然后将这些分词与数据库中索引的分词匹配。结果按相关性评分并作为带有分数的文档 ID 返回。
工作原理
这是搜索过程的逐步说明。
首先,我们使用所有分词器对查询进行分词:
class SearchService
{
public function search(DocumentType $documentType, string $query, ?int $limit = null): array
{
// 1. 使用所有分词器对查询进行分词
$queryTokens = $this->tokenizeQuery($query);
if (empty($queryTokens)) {
return [];
}
如果查询没有产生分词(例如,只有特殊字符),我们返回空结果。
为什么要用相同的分词器对查询进行分词?
不同的分词器产生不同的分词值。如果我们用一个集合索引,用另一个集合搜索,我们会错过匹配。
例如:
- 使用 PrefixTokenizer 索引创建分词:"par", "pars", "parse", "parser"
- 只使用 WordTokenizer 搜索创建分词:"parser"
- 我们会找到 "parser",但不会找到只有 "par" 或 "pars" 分词的文档
- 结果:不完整的匹配,遗漏了相关文档!
解决方案:对索引和搜索使用相同的分词器。相同的分词策略 = 相同的分词值 = 完整的匹配。
这就是为什么 SearchService 和 SearchIndexingService 都接收相同的分词器集合。
接下来,我们提取唯一的分词值。多个分词器可能产生相同的分词值,所以我们去重:
// 2. 提取唯一的分词值
$tokenValues = array_unique(array_map(
fn($token) => $token instanceof Token ? $token->value : $token,
$queryTokens
));
为什么要提取值?我们按分词名称搜索,而不是按权重。我们需要搜索的唯一分词名称。
然后,我们按长度对分词进行排序(最长的优先)。这优先考虑特定匹配:
// 3. 对分词进行排序(最长的优先 - 优先考虑特定匹配)
usort($tokenValues, fn($a, $b) => mb_strlen($b) <=> mb_strlen($a));
为什么要排序?较长的分词更具体。"parser" 比 "par" 更具体,所以我们想先搜索 "parser"。
我们还限制分词数量以防止通过巨大查询进行 DoS 攻击:
// 4. 限制分词数量(防止巨大查询的 DoS)
if (count($tokenValues) > 300) {
$tokenValues = array_slice($tokenValues, 0, 300);
}
为什么要限制?恶意用户可以发送产生数千个分词的查询,导致性能问题。我们保留最长的 300 个分词(已经排序)。
现在,我们执行优化的 SQL 查询。executeSearch() 方法构建 SQL 查询并执行它:
// 5. 执行优化的 SQL 查询
$results = $this->executeSearch($documentType, $tokenValues, $limit);
在 executeSearch() 内部,我们构建带有参数占位符的 SQL 查询,执行它,过滤低分结果,并转换为 SearchResult 对象:
private function executeSearch(DocumentType $documentType, array $tokenValues, int $tokenCount, ?int $limit, int $minTokenWeight): array
{
// 为分词值构建参数占位符
$tokenPlaceholders = implode(',', array_fill(0, $tokenCount, '?'));
// 构建 SQL 查询(在下面的 "SQL 查询" 部分完整展示)
$sql = "SELECT sd.document_id, ... FROM index_entries sd ...";
// 构建参数数组
$params = [
$documentType->value, // document_type
...$tokenValues, // IN 子句的分词值
$documentType->value, // 用于子查询
...$tokenValues, // 用于子查询的分词值
$minTokenWeight, // 最小分词权重
// ... 更多参数
];
// 使用参数绑定执行查询
$results = $this->connection->executeQuery($sql, $params)->fetchAllAssociative();
// 过滤掉标准化分数低的结果(低于阈值)
$results = array_filter($results, fn($r) => (float) $r['score'] >= 0.05);
// 转换为 SearchResult 对象
return array_map(
fn($result) => new SearchResult(
documentId: (int) $result['document_id'],
score: (float) $result['score']
),
$results
);
}
SQL 查询完成繁重的工作:查找匹配的文档,计算分数,并按相关性排序。我们使用原始 SQL 以获得性能和完全控制——我们可以完全按照需要优化查询。
查询使用 JOIN 连接分词和文档,使用子查询进行标准化,使用聚合进行评分,并使用分词名称、文档类型和权重的索引。我们使用参数绑定以确保安全(防止 SQL 注入)。
我们将在下一节看到完整的查询。
主 search() 方法然后返回结果:
// 5. 返回结果
return $results;
}
}
评分算法
评分算法平衡多个因素。让我们逐步分解。
基础分数是所有匹配分词权重的总和:
SELECT
sd.document_id,
SUM(sd.weight) as base_score
FROM index_entries sd
INNER JOIN index_tokens st ON sd.token_id = st.id
WHERE
sd.document_type = ?
AND st.name IN (?, ?, ?) -- 查询分词
GROUP BY sd.document_id
sd.weight:来自 index_entries(field_weight × tokenizer_weight × ceil(sqrt(token_length)))
为什么不乘以 st.weight?分词器权重在索引期间已经包含在 sd.weight 中。来自 index_tokens 的 st.weight 只在完整 SQL 查询的 WHERE 子句中用于过滤(确保至少有一个权重 >= minTokenWeight 的分词)。
这给了我们原始分数。但我们需要的不仅仅是这些。
我们添加了分词多样性提升。匹配更多唯一分词的文档得分更高:
(1.0 + LOG(1.0 + COUNT(DISTINCT sd.token_id))) * base_score
为什么?匹配 5 个不同分词的文档比匹配相同分词 5 次的文档更相关。LOG 函数使这个提升呈对数增长——匹配 10 个分词不会给 10 倍的提升。
我们还添加了平均权重质量提升。具有更高质量匹配的文档得分更高:
(1.0 + LOG(1.0 + AVG(sd.weight))) * base_score
为什么?具有高权重匹配(例如,标题匹配)的文档比具有低权重匹配(例如,内容匹配)的文档更相关。同样,LOG 使这个提升呈对数增长。
我们应用文档长度惩罚。防止长文档占据主导:
base_score / (1.0 + LOG(1.0 + doc_token_count.token_count))
为什么?1000 词的文档不会仅仅因为它有更多分词就自动击败 100 词的文档。LOG 函数使这个惩罚呈对数增长——长 10 倍的文档不会得到 10 倍的惩罚。
最后,我们通过除以最大分数进行标准化:
score / GREATEST(1.0, max_score) as normalized_score
这给了我们 0-1 的范围,使分数在不同查询之间具有可比性。
完整公式看起来像这样:
SELECT
sd.document_id,
(
SUM(sd.weight) * -- 基础分数
(1.0 + LOG(1.0 + COUNT(DISTINCT sd.token_id))) * -- 分词多样性提升
(1.0 + LOG(1.0 + AVG(sd.weight))) / -- 平均权重质量提升
(1.0 + LOG(1.0 + doc_token_count.token_count)) -- 文档长度惩罚
) / GREATEST(1.0, max_score) as score -- 标准化
FROM index_entries sd
INNER JOIN index_tokens st ON sd.token_id = st.id
INNER JOIN (
SELECT document_id, COUNT(*) as token_count
FROM index_entries
WHERE document_type = ?
GROUP BY document_id
) doc_token_count ON sd.document_id = doc_token_count.document_id
WHERE
sd.document_type = ?
AND st.name IN (?, ?, ?) -- 查询分词
AND sd.document_id IN (
SELECT DISTINCT document_id
FROM index_entries sd2
INNER JOIN index_tokens st2 ON sd2.token_id = st2.id
WHERE sd2.document_type = ?
AND st2.name IN (?, ?, ?)
AND st2.weight >= ? -- 确保至少有一个有意义的权重的分词
)
GROUP BY sd.document_id
ORDER BY score DESC
LIMIT ?
为什么要使用带有 st2.weight >= ? 的子查询?这确保我们只包含至少有一个匹配的有意义的分词器权重的分词的文档。没有这个过滤器,只匹配低优先级分词(如权重为 1 的 n-gram)的文档将被包含在内,即使它没有匹配任何高优先级分词(如权重为 20 的单词)。这个子查询过滤掉只匹配噪音的文档。我们想要文档至少匹配一个有意义的分词。
为什么要用这个公式?它平衡了相关性的多个因素。精确匹配得分高,但匹配许多分词的文档也是如此。长文档不会占据主导,但高质量的匹配会。
如果没有权重 10 的结果,我们用权重 1 重试(边缘情况的回退)。
将 ID 转换为文档
搜索服务返回带有文档 ID 和分数的 SearchResult 对象:
class SearchResult
{
public function __construct(
public readonly int $documentId,
public readonly float $score
) {}
}
但我们需要实际的文档,而不仅仅是 ID。我们使用存储库转换它们:
// 执行搜索
$searchResults = $this->searchService->search(
DocumentType::POST,
$query,
$limit
);
// 从搜索结果获取文档 ID(保持顺序)
$documentIds = array_map(fn($result) => $result->documentId, $searchResults);
// 通过 ID 获取文档(保持搜索结果的顺序)
$documents = $this->documentRepository->findByIds($documentIds);
为什么要保持顺序?搜索结果按相关性分数排序。我们希望在显示结果时保持这个顺序。
存储库方法处理转换:
public function findByIds(array $ids): array
{
if (empty($ids)) {
return [];
}
return $this->createQueryBuilder('d')
->where('d.id IN (:ids)')
->setParameter('ids', $ids)
->orderBy('FIELD(d.id, :ids)') // 保持 ID 数组的顺序
->getQuery()
->getResult();
}
FIELD() 函数保持 ID 数组的顺序,所以文档以与搜索结果相同的顺序出现。
结果:你得到了什么
你得到的是一个搜索引擎,它:
- 快速找到相关结果(利用数据库索引)
- 处理拼写错误(n-grams 捕获部分匹配)
- 处理部分单词(前缀分词器)
- 优先考虑精确匹配(单词分词器有最高权重)
- 与现有数据库一起工作(不需要外部服务)
- 易于理解和调试(一切都是透明的)
- 完全控制行为(调整权重,添加分词器,修改评分)
扩展系统
想要添加新的分词器?实现 TokenizerInterface:
class StemmingTokenizer implements TokenizerInterface
{
public function tokenize(string $text): array
{
// 你的词干提取逻辑在这里
// 返回 Token 对象数组
}
public function getWeight(): int
{
return 15; // 你的权重
}
}
在服务配置中注册它,它就会自动用于索引和搜索。
想要添加新的文档类型?实现 IndexableDocumentInterface:
class Comment implements IndexableDocumentInterface
{
public function getIndexableFields(): IndexableFields
{
return IndexableFields::create()
->addField(FieldId::CONTENT, $this->content ?? '', 5);
}
}
想要调整权重?更改配置。想要修改评分?编辑 SQL 查询。一切都在你的控制之下。
结论
这就是你想要的。一个真正能工作的简单搜索引擎。它不花哨,也不需要很多基础设施,但对大多数用例来说,它是完美的。
关键洞察?有时最好的解决方案是你理解的那个。没有魔法,没有黑盒子,只是做它所说的直截了当的代码。
你拥有它,你控制它,你可以调试它。这很有价值。