We often want to use unsorted search patterns, such as hashmap keys, but if we try to build a trie with such a pattern set, we get an error message, and the operation fails.

It is inconvenient to sort a pattern set every time, so it is necessary to address unsorted pattern sets.

In this PR, I attempted to restrict the number of bytes used to represent a mapped code to 2 bytes.

This restriction allows us to

• implement CodeMapper as a 2-byte array, and
• implement the tail of MP-trie with 2-byte alignment (i.e., skipping unpacking integers from a byte sequence).

Summary

Unfortunately, these modifications do NOT provide reasonable improvements. So, I close this PR.

Background

I first investigated the number of character kinds included in several word dictionaries. As the following results show, in practice, it is expected that two bytes are enough to represent a mapped code.

| Dataset | #chars | |---|---:| | jawiki-20220720-all-titles-in-ns0 | 11132 | | zhwiki-20220720-all-titles-in-ns0 | 16829 | | kowiki-20220720-all-titles-in-ns0 | 4780 | | mecab-ipadic-2.7.0 | 5443 | | mecab-ipadic-neologd-0.0.7 | 8904 | | mecab-cedict-20220509 | 14362 | | mecab-kodic-2.1.1 | 9554 | | unidic | 7545 |

Implement CodeMapper as a 2-byte array.

Second, I replaced CodeMapper::table from Vec<u32> into Vec<u16> and performed the benchmark (see https://github.com/daac-tools/crawdad/commit/f24d38df3bcc5c78fb3ab739900b93a558a8dbcf).

This modification is minor, but surprisingly, the search performance was degraded, maybe due to casting mapped codes from u16 to u32.

unidic/exact/crawdad/trie                                                                            
                        time:   [11.060 µs 11.096 µs 11.128 µs]
                        change: [+13.713% +14.242% +14.703%] (p = 0.00 < 0.05)
                        Performance has regressed.
unidic/exact/crawdad/mptrie                                                                            
                        time:   [16.076 µs 16.190 µs 16.293 µs]
                        change: [+4.5033% +5.5107% +6.3737%] (p = 0.00 < 0.05)
                        Performance has regressed.

The improvement in memory was not reasonable.

• Trie: 9.405 MiB -> 9.077 MiB
• MpTrie: 10.967 MiB -> 10.640 MiB

Implement the TAIL of MP-trie with 2-byte alignment

Third, I implemented MpTrie::tails as Vec<u16> to skip unpacking mapped codes from a byte sequence (in addition to the above modification).

The implementation is the same as that in this PR. Unfortunately, we did not see any reasonable improvement.

UniDic

| Version | Exact Match (ns/query) | Memory (MiB) | |---|---:|---:| | Old | 22.591 | 10.967 | | New | 20.763 | 11.723 |

Jawiki-titles

| Version | Exact Match (ns/query) | Memory (MiB) | |---|---:|---:| | Old | 51.710 | 46.148 | | New | 51.579 | 49.414 |

Zhwiki-titles (Chinese)

| Version | Exact Match (ns/query) | Memory (MiB) | |---|---:|---:| | Old | 42.558 | 50.401 | | New | 48.005 | 52.440 |

This PR simplifies the implementation of common prefix search and avoids storing mapped characters in an auxiliary data structure. With this modification, the search speed was improved as follows.

unidic/cps/crawdad/trie time:   [6.9536 ms 6.9676 ms 6.9839 ms]
                        change: [-14.553% -13.982% -13.439%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 2 outliers among 10 measurements (20.00%)
  2 (20.00%) high mild
unidic/cps/crawdad/mptrie
                        time:   [8.1081 ms 8.1424 ms 8.1795 ms]
                        change: [-18.109% -17.562% -16.983%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 1 outliers among 10 measurements (10.00%)
  1 (10.00%) high mild

Discussion

This modification contains the following trade off.

• Pros.
  • Make the API simpler.
  • Remove the auxiliary data structure to store mapped characters.
• Cons.
  • Map the same characters in a haystack repeatedly.
  • Omit byte positions from matched results.

The experimental results indicate that storing and accessing mapped characters in an array is more costly than mapping characters repeatedly. The new simpler API would be easier to use, since it is not necessary to create an instance to store characters. Byte positions are not a necessary result for all users, so there would be no need to provide them in this library.

Currently, common_prefix_searcher() takes a slice generated by map_text(). However, there is no mechanism to link the slice with the trie, so users can give a wrong slice generated by different trie to the common_prefix_searcher():

// example
let keys1 = vec!["アイス", "アイスクリーム"];
let trie1 = MpTrie::from_keys(&keys1).unwrap();
let keys2 = vec!["東京", "京都"];
let trie2 = MpTrie::from_keys(&keys2).unwrap();

let mut mapped = vec![];
trie1.map_text("東京都", &mut mapped);

trie2.common_prefix_searcher(&mapped[1..]);

To avoid this problem, this issue suggests changing common_prefix_searcher() to return an intermediate structure with a mapped text and a reference to the trie:

impl Trie {
   /// Returns an intermediate structure.
   pub fn common_prefix_searcher(&self) -> CommonPrefixSearcher {
       CommonPrefixSearcher {
           trie: self,
           mapped_text: vec![],
       }
   }
}

pub struct CommonPrefixSearcher<'t> {
   trie: &'t Trie,
   mapped_text: Vec<MappedChar>,
}

impl CommonPrefixSearcher {
    /// Updates the haystack.
    pub fn set_text(&mut self, text: &str) {
        self.mapped_text.reset();
        ...
    }

    /// Returns an iterator of the common prefix search.
    pub fn search(&self, range: Range<usize>) -> CommonPrefixSearchIter {
        ...
    }
}

impl Iterator for CommonPrefixSearchIter {
    ...
}

Usage:

let keys = vec!["東京", "京都"];
let trie = MpTrie::from_keys(&keys).unwrap();

let mut searcher = trie.common_prefix_searcher();

searcher.set_text("東京都");
trie.search(1..);

This PR implemented a skipping approach for faster construction.

On UniDic, the construction times were improved from

[crawdad/trie]
heap_bytes: 9795880 bytes, 9.342 MiB
num_elems: 1138688
num_vacants: 119677
vacant_ratio: 0.105
construction: 7.125 [sec]
[crawdad/mptrie]
heap_bytes: 11500152 bytes, 10.967 MiB
num_elems: 1024000
num_vacants: 180321
vacant_ratio: 0.176
construction: 15.686 [sec]

to

[crawdad/trie]
heap_bytes: 9861416 bytes, 9.405 MiB
num_elems: 1146880
num_vacants: 127869
vacant_ratio: 0.111
construction: 3.333 [sec]
[crawdad/mptrie]
heap_bytes: 11500152 bytes, 10.967 MiB
num_elems: 1024000
num_vacants: 180321
vacant_ratio: 0.176
construction: 4.526 [sec]

In this version, I do not add functions to set Builder::num_free_blocks because of avoiding to complicate the API. (i.e., num_free_blocks is always fixed with 16)