# string-trie

**Repository Path**: open-input-method/string-trie

## Basic Information

- **Project Name**: string-trie
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: main
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2026-09-16
- **Last Updated**: 2026-09-20

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# string-trie

MARISA 风格的静态字符串表（Rust 实现，内存驻留，支持二进制序列化），对齐 librime `src/rime/dict/string_table.h` 中 `StringTable` / `StringTableBuilder` 的最小功能集。

## 特性

- **双向查询**：按词条查 ID（`lookup`），按 ID 找回词条（`get_string`）
- **前缀操作**：`common_prefix_match`（公共前缀匹配）、`predict`（前缀预测），覆盖输入法编码查询的核心场景
- **权重排序 ID**：与 marisa 一致，`StringId` 按权重降序分配，高权词条获得更小的 ID，可直接作为数组下标（连续、无空洞）
- **构建器模式**：`StringTableBuilder` 收集词条并去重，`build` 后生成不可变的只读 `StringTable`，构建后查询接口均为 `&self`，可多线程共享
- **二进制序列化**：`to_byte` / `from_byte` 转换字节流，`save` / `load` 保存和加载文件；保留原有版本 1 的小端序格式
- **加载校验**：分配数组前检查计数与数据长度，拒绝缺失根节点、越界 ID、环形连接和词条内容不一致的数据
- **长词条支持**：构建、查询和加载校验均不按词条深度递归，释放临时节点也不递归
- **零依赖**：不依赖任何第三方 crate

## 快速开始

```rust
use string_trie::StringTableBuilder;

let mut builder = StringTableBuilder::new();
builder.add("a", 0.0);
builder.add("an", 0.0);
builder.add("ang", 0.0);
let ni = builder.add("你", - 0.5);

builder.build();
// 构建后取回序号对应的 StringId
let id = builder.id_of(ni).unwrap();

let table = builder.table().unwrap();
assert!(table.has_key("ang"));
assert_eq!(table.lookup("你"), Some(id));
assert_eq!(table.get_string(id), Some("你"));

// 所有是 "ang" 前缀的 key：["a", "an", "ang"]
let _ = table.common_prefix_match("ang");
// 所有以 "a" 为前缀的 key
let _ = table.predict("a");

// 保存到文件，下次使用直接加载，省去重新构建
table.save("table.bin").unwrap();
let loaded = string_trie::StringTable::load("table.bin").unwrap();
assert!(loaded.has_key("ang"));
```

使用时注意：

- `KeyIndex` 定义为 `pub struct KeyIndex(usize)`，只保存词条下标且字段私有；由调用方保证只用于返回它的构建器，并在 `clear` 后丢弃旧序号；不检查序号来源，下标被复用时旧序号可能对应新词条。移动构建器或未清空时重新构建不会使序号失效。
- `id_of` 仅检查构建结果是否可用及下标是否越界；未构建、构建已失效或下标越界时返回 `None`。
- 重复添加保留第一次的权重，不影响已有构建结果；添加新词条则需要重新 `build`。
- 空词条计入总数、可按 ID 取回，但不参与精确查询和前缀匹配；`predict("")` 返回所有非空词条。

运行完整示例：

```sh
cargo run --example build_and_query
```

运行测试（32 个单元测试，包含中文文件读写、异常文件、词条下标与构建状态检查和长词条场景）：

```sh
cargo test
```

## 文档

- 技术说明书（数据结构、算法、API 细节）：[技术说明书.md](技术说明书.md)
- API 文档：`cargo doc --open`

## 许可证

BSD-3-Clause