Clone this repo:
  1. c90fe3d [automerger skipped] Merge "Merge Android 12" am: 0056347f7d -s ours am: 1427082ca9 -s ours am: d6fb3b13f6 -s ours am: 0ba11cd54d -s ours am: d743d2b4f6 -s ours by Xin Li · 2 years, 8 months ago aml_tz4_332714010 aml_tz5_341510010 android13-d2-release android13-d3-s1-release android13-d4-release android13-d4-s1-release android13-d4-s2-release android13-dev android13-frc-adbd-release android13-frc-art-release android13-frc-cellbroadcast-release android13-frc-conscrypt-release android13-frc-documentsui-release android13-frc-extservices-release android13-frc-ipsec-release android13-frc-media-release android13-frc-media-swcodec-release android13-frc-networking-release android13-frc-neuralnetworks-release android13-frc-odp-release android13-frc-os-statsd-release android13-frc-permission-release android13-frc-resolv-release android13-frc-scheduling-release android13-mainline-adservices-release android13-mainline-appsearch-release android13-mainline-go-adbd-release android13-mainline-go-adservices-release android13-mainline-go-appsearch-release android13-mainline-go-art-release android13-mainline-go-cellbroadcast-release android13-mainline-go-conscrypt-release android13-mainline-go-documentsui-release android13-mainline-go-extservices-release android13-mainline-go-ipsec-release android13-mainline-go-media-release android13-mainline-go-media-swcodec-release android13-mainline-go-mediaprovider-release android13-mainline-go-networking-release android13-mainline-go-neuralnetworks-release android13-mainline-go-odp-release android13-mainline-go-os-statsd-release android13-mainline-go-permission-release android13-mainline-go-resolv-release android13-mainline-go-scheduling-release android13-mainline-go-sdkext-release android13-mainline-go-tethering-release android13-mainline-go-tzdata4-release android13-mainline-go-uwb-release android13-mainline-go-wifi-release android13-mainline-tzdata4-release android13-mainline-uwb-release android13-qpr1-release android13-qpr1-s1-release android13-qpr1-s2-release android13-qpr1-s3-release android13-qpr1-s4-release android13-qpr1-s5-release android13-qpr1-s6-release android13-qpr1-s7-release android13-qpr1-s8-release android13-qpr2-b-s1-release android13-qpr2-release android13-qpr2-s1-release android13-qpr2-s10-release android13-qpr2-s11-release android13-qpr2-s12-release android13-qpr2-s2-release android13-qpr2-s3-release android13-qpr2-s5-release android13-qpr2-s6-release android13-qpr2-s7-release android13-qpr2-s8-release android13-qpr2-s9-release android13-qpr3-c-s1-release android13-qpr3-c-s10-release android13-qpr3-c-s11-release android13-qpr3-c-s12-release android13-qpr3-c-s2-release android13-qpr3-c-s3-release android13-qpr3-c-s4-release android13-qpr3-c-s5-release android13-qpr3-c-s6-release android13-qpr3-c-s7-release android13-qpr3-c-s8-release android13-qpr3-release android13-qpr3-s1-release android13-qpr3-s10-release android13-qpr3-s11-release android13-qpr3-s12-release android13-qpr3-s13-release android13-qpr3-s14-release android13-qpr3-s2-release android13-qpr3-s3-release android13-qpr3-s4-release android13-qpr3-s5-release android13-qpr3-s6-release android13-qpr3-s7-release android13-qpr3-s8-release android13-qpr3-s9-release android14-d1-release android14-d1-s1-release android14-d1-s2-release android14-d1-s3-release android14-d1-s4-release android14-d1-s5-release android14-d1-s6-release android14-d1-s7-release android14-d2-release android14-d2-s1-release android14-d2-s2-release android14-d2-s3-release android14-d2-s4-release android14-d2-s5-release android14-dev android14-gsi android14-mainline-adservices-release android14-mainline-appsearch-release android14-mainline-healthfitness-release android14-mainline-uwb-release android14-platform-release android14-qpr1-release android14-qpr1-s2-release android14-qpr2-release android14-qpr2-s1-release android14-qpr2-s2-release android14-qpr2-s3-release android14-qpr2-s4-release android14-qpr2-s5-release android14-release android14-s1-release android14-s2-release android14-security-release android14-tests-release main main-16k main-16k-with-phones master aml_ads_331131000 aml_ads_331418080 aml_ads_331511020 aml_ads_331611190 aml_ads_331710270 aml_ads_331814200 aml_ads_331920180 aml_ads_340915050 aml_ads_341027030 aml_ads_341131050 aml_ads_341316030 aml_ads_341413000 aml_ads_341517040 aml_ads_341615050 aml_ads_341720000 aml_ase_331011020 aml_ase_331112000 aml_ase_331311020 aml_ase_340913000 aml_ase_341113000 aml_ase_341310010 aml_ase_341410000 aml_ase_341510000 aml_cfg_341510000 aml_go_adb_330913000 aml_go_ads_330913000 aml_go_ads_330915000 aml_go_ads_330915100 aml_go_art_330913000 aml_go_ase_330913000 aml_go_cbr_330912000 aml_go_con_330913000 aml_go_doc_330912000 aml_go_ext_330912000 aml_go_ips_330911000 aml_go_med_330913000 aml_go_mpr_330912000 aml_go_net_330913000 aml_go_neu_330912000 aml_go_odp_330912000 aml_go_odp_330913000 aml_go_per_330912000 aml_go_res_330912000 aml_go_sch_330911000 aml_go_sdk_330810000 aml_go_sta_330911000 aml_go_swc_330913000 aml_go_tet_330914010 aml_go_tz4_330912000 aml_go_uwb_330912000 aml_go_wif_330911000 aml_hef_341114030 aml_hef_341311010 aml_hef_341415040 aml_hef_341512030 aml_hef_341613000 aml_hef_341717050 aml_odp_341610000 aml_odp_341717000 aml_rkp_341012000 aml_rkp_341015010 aml_rkp_341114000 aml_rkp_341311000 aml_rkp_341510000 aml_tz4_331012000 aml_tz4_331012040 aml_tz4_331012050 aml_tz4_331314010 aml_tz4_331314020 aml_tz4_331314030 aml_tz4_331910000 aml_tz4_332714010 aml_tz4_332714050 aml_tz4_332714070 aml_tz5_341510010 aml_tz5_341510050 aml_tz5_341510070 aml_uwb_330810010 aml_uwb_331015040 aml_uwb_331115000 aml_uwb_331310030 aml_uwb_331410010 aml_uwb_331611010 aml_uwb_331613010 aml_uwb_331820070 aml_uwb_331910010 aml_uwb_341011000 aml_uwb_341111010 aml_uwb_341310030 aml_uwb_341310300 aml_uwb_341511050 aml_uwb_341513070 aml_uwb_341710010 android-13.0.0_r16 android-13.0.0_r17 android-13.0.0_r18 android-13.0.0_r19 android-13.0.0_r20 android-13.0.0_r21 android-13.0.0_r22 android-13.0.0_r23 android-13.0.0_r24 android-13.0.0_r27 android-13.0.0_r28 android-13.0.0_r29 android-13.0.0_r30 android-13.0.0_r32 android-13.0.0_r33 android-13.0.0_r34 android-13.0.0_r35 android-13.0.0_r36 android-13.0.0_r37 android-13.0.0_r38 android-13.0.0_r39 android-13.0.0_r40 android-13.0.0_r41 android-13.0.0_r42 android-13.0.0_r43 android-13.0.0_r44 android-13.0.0_r45 android-13.0.0_r46 android-13.0.0_r47 android-13.0.0_r48 android-13.0.0_r49 android-13.0.0_r50 android-13.0.0_r51 android-13.0.0_r52 android-13.0.0_r53 android-13.0.0_r54 android-13.0.0_r55 android-13.0.0_r56 android-13.0.0_r57 android-13.0.0_r58 android-13.0.0_r59 android-13.0.0_r60 android-13.0.0_r61 android-13.0.0_r62 android-13.0.0_r63 android-13.0.0_r64 android-13.0.0_r65 android-13.0.0_r66 android-13.0.0_r67 android-13.0.0_r68 android-13.0.0_r69 android-13.0.0_r70 android-13.0.0_r71 android-13.0.0_r72 android-13.0.0_r73 android-13.0.0_r74 android-13.0.0_r75 android-13.0.0_r76 android-13.0.0_r77 android-13.0.0_r78 android-13.0.0_r79 android-13.0.0_r80 android-13.0.0_r81 android-13.0.0_r82 android-13.0.0_r83 android-14.0.0_r1 android-14.0.0_r10 android-14.0.0_r11 android-14.0.0_r12 android-14.0.0_r13 android-14.0.0_r14 android-14.0.0_r15 android-14.0.0_r16 android-14.0.0_r17 android-14.0.0_r18 android-14.0.0_r19 android-14.0.0_r2 android-14.0.0_r20 android-14.0.0_r21 android-14.0.0_r22 android-14.0.0_r23 android-14.0.0_r24 android-14.0.0_r25 android-14.0.0_r26 android-14.0.0_r27 android-14.0.0_r28 android-14.0.0_r29 android-14.0.0_r3 android-14.0.0_r30 android-14.0.0_r31 android-14.0.0_r32 android-14.0.0_r33 android-14.0.0_r34 android-14.0.0_r35 android-14.0.0_r36 android-14.0.0_r37 android-14.0.0_r38 android-14.0.0_r39 android-14.0.0_r4 android-14.0.0_r40 android-14.0.0_r41 android-14.0.0_r42 android-14.0.0_r43 android-14.0.0_r44 android-14.0.0_r45 android-14.0.0_r5 android-14.0.0_r6 android-14.0.0_r7 android-14.0.0_r8 android-14.0.0_r9 android-cts-14.0_r1 android-cts-14.0_r2 android-cts-14.0_r3 android-cts-14.0_r4 android-platform-14.0.0_r1 android-platform-14.0.0_r2 android-platform-14.0.0_r3 android-platform-14.0.0_r4 android-platform-14.0.0_r5 android-platform-14.0.0_r6 android-platform-14.0.0_r7 android-security-14.0.0_r1 android-security-14.0.0_r2 android-security-14.0.0_r3 android-security-14.0.0_r4 android-security-14.0.0_r5 android-security-14.0.0_r6 android-security-14.0.0_r7 android-security-14.0.0_r8 android-u-beta-1-gpl android-vts-14.0_r1 android-vts-14.0_r2 android-vts-14.0_r3 android-vts-14.0_r4 frc_340818110 frc_340818170 frc_340819010 frc_340819020 frc_340819030 frc_340819190 frc_340819220 frc_340819280 frc_340821000 t_frc_adb_330444000 t_frc_art_330443060 t_frc_ase_330444010 t_frc_cbr_330443000 t_frc_con_330443020 t_frc_doc_330443000 t_frc_doc_330443060 t_frc_doc_330543000 t_frc_ext_330443000 t_frc_ips_330443010 t_frc_med_330443030 t_frc_net_330443000 t_frc_neu_330443000 t_frc_neu_330443030 t_frc_odp_330442000 t_frc_odp_330442040 t_frc_per_330444010 t_frc_res_330443000 t_frc_sch_330443010 t_frc_sch_330443040 t_frc_sta_330443010 t_frc_swc_330443010 t_frc_swc_330443040 t_frc_tz4_330443010
  2. d743d2b [automerger skipped] Merge "Merge Android 12" am: 0056347f7d -s ours am: 1427082ca9 -s ours am: d6fb3b13f6 -s ours am: 0ba11cd54d -s ours by Xin Li · 2 years, 8 months ago
  3. 0ba11cd [automerger skipped] Merge "Merge Android 12" am: 0056347f7d -s ours am: 1427082ca9 -s ours am: d6fb3b13f6 -s ours by Xin Li · 2 years, 8 months ago android-s-qpr3-beta-1 android-s-v2-beta-3 android-t-preview-1 android-s-qpr3-beta-1 android-s-v2-beta-3 android-t-beta-3 android-t-preview-1 android-t-preview-2
  4. d6fb3b1 [automerger skipped] Merge "Merge Android 12" am: 0056347f7d -s ours am: 1427082ca9 -s ours by Xin Li · 2 years, 8 months ago
  5. 1427082 [automerger skipped] Merge "Merge Android 12" am: 0056347f7d -s ours by Xin Li · 2 years, 8 months ago

README

Project name

marisa-trie

Project summary

MARISA: Matching Algorithm with Recursively Implemented StorAge

Latest version

0.2.6

Description

Matching Algorithm with Recursively Implemented StorAge (MARISA) is a static and space-efficient trie data structure. And libmarisa is a C++ library to provide an implementation of MARISA. Also, the package of libmarisa contains a set of command line tools for building and operating a MARISA-based dictionary.

A MARISA-based dictionary supports not only lookup but also reverse lookup, common prefix search and predictive search.

  • Lookup is to check whether or not a given string exists in a dictionary.
  • Reverse lookup is to restore a key from its ID.
  • Common prefix search is to find keys from prefixes of a given string.
  • Predictive search is to find keys starting with a given string.

The biggest advantage of libmarisa is that its dictionary size is considerably more compact than others. See below for the dictionary size of other implementations.

  • Input
    • Source: enwiki-20121101-all-titles-in-ns0.gz
    • Contents: all page titles of English Wikipedia (Nov. 2012)
    • Number of keys: 9,805,576
    • Total size: 200,435,403 bytes (plain) / 54,933,690 bytes (gzipped)
ImplementationSize (bytes)Remarks
darts-clone376,613,888Compacted double-array trie
tx-trie127,727,058LOUDS-based trie
marisa-trie50,753,560MARISA trie

Documentation

Build instructions

You can get the latest version via git clone. Then, you can generate a configure script via autoreconf -i. After that, you can build and install libmarisa and its command line tools via configure and make. For details, see also documentation in docs.

$ git clone https://github.com/s-yata/marisa-trie.git
$ cd marisa-trie
$ autoreconf -i
$ ./configure --enable-native-code
$ make
$ make install

Source code license

  • The BSD 2-clause License
  • The LGPL 2.1 or any later version