cpp-fstlib

C++17 header-only FST (finite state transducer) library. We can use it as Trie data structure. This library uses the algorithm "Minimal Acyclic Subsequential Transducers".

Play cpp-fstlib with cli

> git clone http://github/yhirose/cpp-fstlib
> cd cpp-fstlib
> make build && cd build
> cmake .. && make
> ./cmd/fst compile /usr/share/dict/words words.fst

> ./cmd/fst search words.fst hello
83713

> ./cmd/fst prefix words.fst helloworld
h: 81421
he: 82951
hell: 83657
hello: 83713

> ./cmd/fst longest words.fst helloworld
hello: 83713

> ./cmd/fst predictive words.fst predictiv
predictive: 153474
predictively: 153475
predictiveness: 153476

> ./cmd/fst fuzzy words.fst fuzzy -ed 2 // Edit distance 2
Suzy: 195759
buzz: 28064
buzzy: 28076
...

> ./cmd/fst spellcheck words.fst thier
their: 0.946667
thir: 0.762667
tier: 0.752
thief: 0.736
trier: 0.704

API reference

namespace fst {

enum class Result { Success, EmptyKey, UnsortedKey, DuplicateKey };

std::pair<Result, size_t /* error input index */> compile<uint32_t>(
  const std::vector<std::pair<std::string, uint32_t>> &input,
  std::ostream &os,
  bool sorted
);

std::pair<Result, size_t /* error input index */> compile<std::string>(
  const std::vector<std::pair<std::string, std::string>> &input,
  std::ostream &os
);

std::pair<Result, size_t /* error input index */> compile(
  const std::vector<std::string> &key_only_input,
  std::ostream &os,
  bool need_output, // true: map, false: set
  bool sorted
);

// Checks the whole byte code against its checksum (reads all of it)
bool verify(const char *byte_code, size_t byte_code_size);

template <typename output_t> class map {
public:
  map(const char *byte_code, size_t byte_code_size);

  operator bool() const;

  bool contains(std::string_view sv) const;

  output_t operator[](std::string_view sv) const;

  output_t at(std::string_view sv) const;

  bool exact_match_search(std::string_view sv, output_t &output) const;

  std::vector<std::pair<size_t length, output_t output>>
  common_prefix_search(std::string_view sv) const;

  size_t longest_common_prefix_search(std::string_view sv, output_t &output) const;

  std::vector<std::pair<std::string, output_t>>
  predictive_search(std::string_view sv) const;

  std::vector<std::pair<std::string, output_t>>
  edit_distance_search(std::string_view sv, size_t max_edits) const;

  std::vector<std::tuple<double, std::string, output_t>>
  suggest(std::string_view word) const;

  // T must implement: void step(char), bool is_match() const, bool can_match() const
  template <typename T>
  void custom_search(const T &atm,
                     std::function<void(const std::string &, const output_t &)> callback) const;
}

class set {
public:
  set(const char *byte_code, size_t byte_code_size);

  operator bool() const;

  bool contains(std::string_view sv) const;

  std::vector<size_t> common_prefix_search(std::string_view sv) const;

  size_t longest_common_prefix_search(std::string_view sv) const;

  std::vector<std::string> predictive_search(std::string_view sv) const;

  std::vector<std::string>
  edit_distance_search(std::string_view sv, size_t max_edits) const;

  std::vector<std::pair<double, std::string>>
  suggest(std::string_view word) const;

  // T must implement: void step(char), bool is_match() const, bool can_match() const
  template <typename T>
  void custom_search(const T &atm,
                     std::function<void(const std::string &)> callback) const;
}

} // namespace fst

API usage

const std::vector<std::pair<std::string, std::string>> items = {
  {"hello", "こんにちは!"},
  {"world", "世界!"},
  {"hello world", "こんにちは世界!"}, // incorrect sort order entry...
};

std::stringstream out;
auto sorted = false; // ask fst::compile to sort entries
auto [result, error_line] = fst::compile<std::string>(items, out, sorted);

if (result == fst::Result::Success) {
  const auto& byte_code = out.str();
  fst::map<std::string> matcher(byte_code.data(), byte_code.size());

  if (matcher) {
    assert(matcher.contains("hello world"));
    assert(!matcher.contains("Hello World"));
    assert(matcher["hello"] == "こんにちは!");

    auto prefixes = matcher.common_prefix_search("hello world!");
    assert(prefixes.size() == 2);
    assert(prefixes[0].first == 5);
    assert(prefixes[0].second == "こんにちは!");
    assert(prefixes[1].first == 11);
    assert(prefixes[1].second == "こんにちは世界!");

    std::string output;
    auto length = matcher.longest_common_prefix_search("hello world!", output);
    assert(length == 11);
    assert(output == "こんにちは世界!");

    auto predictives = matcher.predictive_search("he");
    assert(predictives.size() == 2);
    assert(predictives[0].first == "hello");
    assert(predictives[0].second == "こんにちは!");
    assert(predictives[1].first == "hello world");
    assert(predictives[1].second == "こんにちは世界!");

    std::cout << "[Edit distance 1]" << std::endl;
    for (auto [k, o]: matcher.edit_distance_search("hellow", 1)) {
      std::cout << "key: " << k << " output: " << o << std::endl;
    }

    std::cout << "[Suggestions]" << std::endl;
    for (auto [r, k, o]: matcher.suggest("hellow")) {
      std::cout << "ratio: " << r << " key: " << k << " output: " << o << std::endl;
    }

    // Custom automaton: implement step(char), is_match() const, can_match() const,
    // then plug it into custom_search() to drive the FST traversal with your own logic.
    // (LevenshteinAutomaton, used internally by edit_distance_search, is a
    // fuller example of the same contract.)
    struct MaxLengthAutomaton {
      size_t max_len;
      size_t len = 0;
      void step(char) { len++; }
      bool is_match() const { return len <= max_len; }
      bool can_match() const { return len <= max_len; }
    };

    std::cout << "[Custom search: words up to 6 chars long]" << std::endl;
    matcher.custom_search(MaxLengthAutomaton{6}, [](const auto &k, const auto &o) {
      std::cout << "key: " << k << " output: " << o << std::endl;
    });
  }
}

[Edit distance 1]
key: hello output: こんにちは
[Suggestions]
ratio: 0.810185 key: hello output: こんにちは
ratio: 0.504132 key: hello world output: こんにちは世界!
ratio: 0.0962963 key: world output: 世界!
[Custom search: words up to 6 chars long]
key: hello output: こんにちは!
key: world output: 世界!

Byte code format and corruption

A byte code ends with a trailer that has its size, a checksum (XXH64) and a format version.

[records][header][body size: 8][body xxh64: 8][version: 4]["FST\x07"]

fst::map and fst::set check the trailer and the header when they open a byte code, and operator bool() returns false if it is truncated, has extra bytes, is not a byte code, or was made by an incompatible version of this library. This check is O(1) and doesn't read the rest of the byte code, so opening one stays cheap, even when it is large and memory mapped.

fst::verify also checks the whole byte code against the checksum, which reads all of it. Call it before opening a byte code from a source that you don't trust to keep the bytes intact. Searching a byte code whose contents are corrupted is undefined behavior.

if (!fst::verify(byte_code.data(), byte_code.size())) {
  // corrupted
}

NOTE: Byte codes made before the trailer was introduced are rejected as invalid. Please compile them again from the original input.

Benchmark

Measured with benchmark/main.cc on /usr/share/dict/words (235,976 keys, Apple M1 Pro, -O3). Build is the time to compile the dictionary, and the search columns are the total time of looking up all 235,976 keys 5 times.

Library	Structure	Size	Build	Exact match	Common prefix
darts-clone	double array	8,755,880	64 ms	22 ms	23 ms
ux-trie	LOUDS	895,510	67 ms	1,161 ms	1,041 ms
marisa-trie	LOUDS	743,368	69 ms	305 ms	313 ms
BurntSushi/fst (Rust)	FST	1,501,442	90 ms	540 ms	n/a
cpp-fstlib (map<uint32_t>)	FST	1,070,382	125 ms	215 ms	216 ms
cpp-fstlib (auto index)	FST	985,753	118 ms	220 ms	220 ms

The map<uint32_t> row stores an arbitrary uint32_t value per key, while the auto index row assigns sequential ids to the sorted keys, which is what the trie libraries above provide.

The BurntSushi/fst row was measured separately with benchmark/fst-rust (cargo run --release), a small Rust harness that builds a fst::Map with sequential ids as values and times Map::get the same way. It's a different process/toolchain (Rust, not linked into benchmark/main.cc), so treat the comparison as indicative rather than exact; its Map type has no built-in common-prefix search, so that column is n/a.

License

MIT license (© 2022 Yuji Hirose)