Flutter前缀树（Trie）数据结构插件itrie的使用

Flutter前缀树（Trie）数据结构插件itrie的使用

简介

ITrie 是一个高效的、不可变且栈安全的前缀树（Trie）数据结构的 Dart 实现。前缀树非常适合用于自动补全、文本搜索、拼写检查等场景，尤其是在处理字符串和前缀时。

安装

在 pubspec.yaml 文件中添加 itrie 依赖：

dependencies:
  itrie: ^0.0.1

使用方法

构造函数

ITrie 可以通过任何 Iterable 或者使用 empty 构造函数来创建：

/// 创建一个空的 [ITrie]，值类型为 [int]
final empty = ITrie<int>.empty();
final copy = empty.insert("key", 10);

/// 从包含 (String, T) 记录的 [Iterable] 创建 [ITrie]
final fromIterable = ITrie.fromIterable([("key", 10)]);

Iterable

ITrie 继承自 Iterable，因此可以使用所有 Iterable API 中的方法，例如 map、fold、every、iterator 等。

不可变操作

ITrie 是不可变的，所有的修改操作都会返回一个新的 ITrie 实例，而不会修改原始的 ITrie。以下是一些常见的修改操作：

final itrie = ITrie<int>.empty();

// 插入键值对
final insert = itrie.insert("key", 10);

// 删除键值对
final remove = itrie.remove("key");

// 修改键值对
final modify = itrie.modify("key", (value) => value + 1);

// 批量插入多个键值对
final insertMany = itrie.insertMany([("key2", 20)]);

// 批量删除多个键
final removeMany = itrie.removeMany(["key"]);

获取器

ITrie 提供了多种方法来根据键或前缀提取值：

final itrie = ITrie<int>.empty();

// 根据键获取值
final getV = itrie.get("key");

// 获取最长前缀
final longestPrefixOf = itrie.longestPrefixOf("keys");

// 获取具有指定前缀的所有键值对
final withPrefix = itrie.withPrefix("ke");

// 获取具有指定前缀的所有键
final keysWithPrefix = itrie.keysWithPrefix("ke");

// 获取具有指定前缀的所有值
final valuesWithPrefix = itrie.valuesWithPrefix("ke");

// 获取所有键
final keys = itrie.keys;

// 获取所有值
final values = itrie.values;

// 获取元素数量
final length = itrie.length;

// 检查是否存在指定键
final has = itrie.has("key");

属性

不可变性

ITrie 是不可变的，所有的修改操作都会返回一个新的 ITrie 实例。例如：

final itrie = ITrie<int>.empty();
final newITrie = itrie.insert("key", 10); /// 👈 `insert` 返回一个新的 [ITrie]

expect(itrie.length, 0); /// 👈 原始 `itrie` 未被修改
expect(newITrie.length, 1);

栈安全性

ITrie 不使用递归，因此无论执行多少操作或包含多少元素，都不会导致栈溢出问题。

空间效率

ITrie 内部实现为三元搜索树（Ternary Search Trie），这种数据结构允许任意大小的字符集，并且比其他前缀树实现更节省空间。

示例代码

以下是一个完整的示例代码，展示了如何使用 ITrie 进行单词查找和自动补全：

import 'dart:convert';
import 'dart:io';

import 'package:itrie/itrie.dart';

void main() async {
  /// 读取单词文件
  final file = File('./example/words.txt');
  Stream<String> lines = file.openRead().transform(utf8.decoder).transform(
        LineSplitter(),
      );

  try {
    // 读取所有单词并过滤掉不符合条件的单词
    final sourceList = await lines.toList();
    final selection = sourceList
        .where(
          (key) => key.length >= 2 && RegExp(r'^[A-Za-z]+$').hasMatch(key),
        )
        .map((e) => e.toLowerCase());

    // 将筛选后的单词保存到新文件
    await File('./example/selection.txt')
        .writeAsString(selection.toList().join("\n"));

    // 创建 ITrie，将每个单词作为键，单词长度作为值
    final itrie = ITrie<int>.fromIterable(
      selection
          .map(
            (key) => (key.toLowerCase(), key.length),
          )
          .toList(),
    );

    print("Loaded ${itrie.length} words");

    // 交互式命令行，用户可以输入单词进行查找
    while (true) {
      print("Search a word");
      final line = stdin.readLineSync(encoding: utf8);
      if (line != null) {
        if (line == "q") {
          break;
        }

        // 查找用户输入的单词
        final result = itrie.get(line);
        if (result != null) {
          print("Found word: $line, Length: $result");
        } else {
          print("Word not found: $line");
        }
      }
    }
  } catch (e) {
    print('Error: $e');
  }
}