DEIM Forum 2017 G4-2

จࣈྻࣙॻΛ༻͍ͨޮ཰తͳจࣈྻࣙॻѹॖͷ‫ݕ‬౼ͱධՁ
ਆా

फ़հ†

৿ా

࿨޺†

ᔖా

ਖ਼༤†

† ಙౡେֶେֶӃઌ୺ٕज़Պֶ‫ڭ‬ҭ෦ ˟ 770–8506 ಙౡ‫ݝ‬ಙౡࢢೆৗࡾౡொ 2–1
E-mail: †shnsk.knd@gmail.com, ††{kam,fuketa}@is.tokushima-u.ac.jp͋Β·͠จࣈྻू߹Λอ؅͢ΔͨΊͷσʔλߏ଄Ͱ͋Δจࣈྻࣙॻʹؔͯ͠ɼۙ೥ɼଟ͘ͷ༻్ͰίϯύΫτੑ͕‫ٻ‬ΊΒΕΔͱ͍͏࣮ྫ͕ใࠂ͞Ε͍ͯΔɽ·ͨɼͦͷഎ‫ʹܠ‬Ԡͯ͡ɼTrie ΍ Front-Coding ͳͲͷࣙॻΛ࣮‫͢ݱ‬ΔͨΊͷ༏Εٕͨ๏ʹɼจ๏ѹॖͳͲͷ‫ͳྗڧ‬σʔλѹॖΛ૊Έ߹Θͤͨѹॖจࣈྻࣙॻ͕ఏҊ͞Ε͍ͯΔɽຊߘͰ͸ɼ‫ط‬ଘͷѹॖจࣈྻࣙॻͷվྑΛ໨తͱ͠ɼจࣈྻࣙॻͷѹॖʹจࣈྻࣙॻΛ༻͍Δͱ͍͏ํࡦʹ‫ߏॻ͍ࣙͨͮج‬଄ΛఏҊ͢Δɽ࣮σʔλΛ༻͍࣮ͨ‫ݧ‬ΑΓɼఏҊʹΑΔจࣈྻࣙॻ͸ Re-Pair ʹΑΓѹॖͨࣙ͠ॻͱൺ΂ɼϝϞϦޮ཰΍‫ݕ‬ࡧɾ෮‫ݩ‬଎౓ͷτϨʔυΦϑʹؔͯ͠ಉ౳ͷੑೳΛࣔͭͭ͠ɼ୹͍࣌ؒͰߏஙͰ͖Δ͜ͱΛࣔͨ͠ɽΩʔϫʔυ ѹॖจࣈྻࣙॻɼTrieɼFront-Codingɼѹॖσʔλߏ଄

1. ͸ ͡ Ί ʹจࣈྻࣙॻͱ͸ɼจࣈྻͷू߹Λอ؅͢ΔͨΊͷσʔλߏ଄Ͱ͋Γɼ֤จࣈྻʹର͠‫ݻ‬༗ͷ ID ΛׂΓ౰ͯΔɽ͢ͳΘͪɼจ͘͠͸ѹॖίετͷ௿͍ҟͳΔσʔλѹॖͷར༻ͳͲ͕ߟ͑Β
ΕΔ͕ɼͦΕͰ͸ΦϦδφϧͷ Re-Pair ΄Ͳͷѹॖ཰͕ಘΒΕͳ͍ͱ͍͏δϨϯϚʹؕΔɽ͜ͷ໰୊͸ɼѹॖจࣈྻࣙॻͷߋ
ͳΔ࣮༻Խʹ޲͚ͨվળ͢΂͖఺ͷ 1 ͭͱ͍͑Δɽࣈྻͷೖྗʹର͠ɼͦͷ ID Λใࠂ͢Δ Lookup ͱɼID ͷೖྗຊ‫Ͱڀݚ‬͸ɼจࣈྻࣙॻͷѹॖʹจࣈྻࣙॻΛ༻͍Δͱ͍͏

ʹର͠ɼͦͷจࣈྻΛใࠂ͢Δ Access ͷ 2 ͭͷૢ࡞Λఏ‫͢ڙ‬ํࡦʹ‫͖ͮج‬ɼ͜͏ͨ͠໰୊ͷվળɼ‫طͼٴ‬ଘͷѹॖจࣈྻࣙ

Δσʔλߏ଄Ͱ͋Δɽࣗવ‫ॲޠݴ‬ཧ΍৘ใ‫ࡧݕ‬ɼηϚϯςΟο

ॻͷੑೳ޲্Λ໨ࢦ͢ɽ͜ͷํࡦʹؔͯ͠ಈ‫ͨͬͳͱػ‬ͷ͕ɼ໼Ϋɾ΢ΣϒɼόΠΦΠϯϑΥϚςΟΫεɼ஍ཧ৘ใγεςϜͳా [5] ʹΑΓఏҊ͞Εͨࣙॻߏ଄Ͱ͋Δɽ͜ͷࣙॻͰ͸ Trie ΛͲͷ਺ଟ͘ͷ༻్ʹ͓͍ͯ༻͍ΒΕ͍ͯΔɽҰํͰɼۙ೥Ͱ͸ϕʔεͱ͠ɼ෦෼తʹ‫ݱ‬ΕΔจࣈྻΛ࠶‫ؼ‬తʹ Trie ࣙॻʹΑΓେ‫ن‬໛σʔλʹରࣙ͠ॻຊମͷαΠζ͕໰୊ͱͳΔࣄྫ͕ෳ਺

ѹॖ͢Δͱ͍͏ํ๏Ͱߴ͍ϝϞϦޮ཰Λୡ੒͍ͯ͠Δɽ͜ͷΑใࠂ͞Ε͓ͯΓ [1]ɼϝϞϦޮ཰ͷྑ͍ࣙॻߏ଄ɼ͍ΘΏΔѹ͏ʹࣙॻͷѹॖʹࣙॻΛ༻͍Δͱ͍͏ํ๏͸ɼ‫ط‬ଘͷ Re-PairॖจࣈྻࣙॻͷఏҊ͕ଟ͘ͳ͞Ε͍ͯΔ [1–5]ɽ

ͳͲʹΑΓѹॖ͞ΕΔࣙॻʹରͯ͠΋ద༻Ͱ͖ɼ৽ͨͳѹॖͷจࣈྻࣙॻͷѹॖʹؔͯ͠ɼςΩετσʔλʹର͢Δ‫ྗڧ‬ͳѹॖख๏Λద༻͢Δํࡦ͕ɼۙ೥ͷ‫Ͱڀݚ‬͸ଟ͘‫ݟ‬ΒΕΔɽ
ྫ͑͹ɼMartı́nez-Prieto Β [1] ͸ɼจࣈྻࣙॻΛ࣮‫͢ݱ‬Δͨ
Ίͷ༷ʑͳٕ๏ʹ‫ط‬ଘͷσʔλѹॖΛ૊Έ߹ΘͤΔ͜ͱʹΑखஈͱͳΓಘΔɽͦ͜ͰຊߘͰ͸ɼ͜ͷํࡦʹ‫ߏॻ͍ࣙͨͮج‬଄Λ͍͔ͭ͘ఏҊ͠ɼ࣮‫ʹݧ‬ΑΓධՁΛ༩͑Δɽ

2. ४

උ

ΓɼϝϞϦޮ཰ʹ༏ΕͨࣙॻΛෳ਺‫ݸ‬ఏҊ͍ͯ͠ΔɽதͰ΋ɼຊઅͰ͸ɼࣙॻΛ࣮૷͢Δ্ͰඞཁͱͳΔσʔλߏ଄Λ؆୯

Front-Coding [6] Λϕʔεͱͨࣙ͠ॻͷੑೳ͕ߴ͘ɼ෦෼తʹʹ঺հ͢Δɽ͸͡Ίʹɼ‫ج‬ຊతͳఆٛΛҎԼʹ༩͑Δɽจࣈ͕‫ݱ‬ΕΔจࣈྻʹର͠σʔλѹॖΛద༻͢Δ͜ͱͰߴ͍ϝϞϦऔΓಘΔ஋ͷू߹ Σ ΛΞϧϑΝϕοτͱ͍͍ɼͦͷαΠζΛ

ޮ཰Λୡ੒͍ͯ͠ΔɽGrossi ͱ Ottaviano [2] ͸ɼTrie [7] Λ

σ = |Σ| ͱද͢ɽର਺ͷఈ͸ 2 Ͱ౷Ұ͢Δɽ

ϕʔεʹ Path Decomposion [8] ͱ‫ݺ‬͹ΕΔٕ๏Λ༻͍Δ͜ͱ
ͰɼΩϟογϡޮ཰ʹ༏ΕͨࣙॻΛ࣮‫͍ͯ͠ݱ‬Δɽ͜ͷࣙॻߏ଄ʹ͓͍ͯ΋ɼ‫ط‬ଘͷσʔλѹॖͱ૊Έ߹ΘͤΔ͜ͱͰߴ͍ϝϞϦޮ཰Λ࣮‫͍ͯ͠ݱ‬Δɽ͜ͷΑ͏ʹɼςΩετσʔλʹର͢Δ‫ط‬ଘͷѹॖख๏Λ༻͍ͨจࣈྻࣙॻ͕ෳ਺ఏҊ͞Ε͍ͯΔɽதͰ΋ɼTrie ΍ Front-

Coding ͳͲΛϕʔεͱͯ͠ߏஙͨࣙ͠ॻ಺ʹ෦෼తʹ‫ݱ‬ΕΔ

2. 1 Rank/Select ࣙॻϏοτྻ B[1...n] ʹର͠ɼRank/Select ͱ‫ݺ‬͹ΕΔ‫ج‬ຊతͳ

2 ͭͷૢ࡞Λಋೖ͢Δɽ
••

Rankb (B, i)ɿB[1...i] தͷ b ∈ {0, 1} ͷ਺Λฦ͢ɽ

Selectb (B, i)ɿi ൪໨ͷ b ∈ {0, 1} ͕ग़‫͢ݱ‬ΔҐஔΛฦ͢ɽ͜ΕΒͷૢ࡞͸ɼo(n) Ϗοτͷิॿσʔλߏ଄ΛՃ͑Δ͜ͱʹΑͬͯɼఆ਺࣌ؒͰ࣮ߦͰ͖Δ [10]ɽจࣈྻʹɼRe-Pair [9] ͱ‫ݺ‬͹ΕΔจ๏ѹॖΛద༻͢Δ͜ͱʹΑ

2. 2 LOUDS ද‫ݱ‬ΓಘΒΕΔѹॖจࣈྻࣙॻ͸ɼ൚༻తʹߴ͍ϝϞϦޮ཰Λୡ੒

LOUDSʢLevel-Ordered Unary Degree Sequenceʣ[10] ͸͠ɼLookup/Access ͷ࣮ߦ࣌ؒʹؔͯ͠΋༏Ε͍ͯΔɽҰํɼॱং໦Λද‫͢ݱ‬ΔͨΊͷ؆ܿσʔλߏ଄ɼ͍ΘΏΔ؆ܿ໦ͷ 1

Re-Pair ʹΑΔѹॖ͸ೖྗจࣈྻ௕ʹର͠ઢ‫Ͱؒ࣌ܗ‬ಈ࡞͢Δ

छͰ͋ΔɽLOUDS Ͱ͸ɼࢠΛ d ‫ͭ࣋ݸ‬અ఺Λ d ‫ݸ‬ͷ ‘1’ ͱ 1΋ͷͷɼ࣮ࡍʹ͸େ෯ͳ࣌ؒͱ࡞‫ྖۀ‬ҬΛཁ͠ɼRe-Pair Λ༻‫ݸ‬ͷ ‘0’ ͷ࿈݁ʹΑΓද͠ɼ͜ΕΒΛ෯༏ઌʹ࿈݁͢Δ͜ͱʹΑ͍ͨࣙॻͷߏஙίετ͸ඇৗʹେ͖͍ͱ͍͏໰୊΋ಉ࣌ʹଘࡏΓಘΒΕΔϏοτྻʹΑΓ໦Λද‫͢ݱ‬Δɽ͜ͷͱ͖ɼࠜͷ਌ͷ͢ΔɽվળͷͨΊʹɼѹॖίετͷ໘Ͱͷ Re-Pair ͷվྑɼ΋Α͏ʹৼΔ෣͏εʔύʔϧʔτͱͯ͠ɼϏοτྻͷઌ಄ʹ “10”Λ෇༩͢Δɽઅ఺ͷҠಈ͸ɼϏοτྻ্ͷ Rank/Select Λհ͠1ide࣮ͯ‫͞ݱ‬ΕΔͨΊɼԾʹ໦ͷઅ఺਺Λ n ͱͨ͠ͱ͖ɼͦͷϝϞt32Ϧ࢖༻ྔ͸ 2n + o(n) ϏοτͱͳΔɽ

a

2. 3 DFUDS ද‫ݱ‬

5

4

DFUDSʢDepth-First Unary Degree Sequenceʣ[11] ͸ ɼ

s

a

9

10

11

ং໦Λද‫͢ݱ‬ΔɽDFUDS Ͱ͸ɼࢠΛ d ‫ͭ࣋ݸ‬અ఺Λ d ‫ݸ‬ͷ‘(’ ͱ 1 ‫ݸ‬ͷ ‘)’ ͷ࿈݁ʹΑΓද͢ɽͦͯ͠ɼ͜ΕΒΛਂ͞༏ઌ

rie

ie
7

6

l

LOUDS ͱಉ͘͡؆ܿ໦ͷ 1 छͰ͋Γɼ‫ྻހׅ‬Λ༻͍ͯॱ

e

ology

8

ch
12
ie

nology1314(a) C-Trieɽ֤จࣈྻͷऴ୺ʹҐஔ͢Δઅ఺͕࢛֯

ॱʹ࿈݁͠ɼઌ಄ʹ ‘(’ Λ௥Ճͨ͠‫ʹྻހׅ‬ΑΓ໦Λද‫͢ݱ‬Δɽ

Ͱඳ͔Ε͍ΔDFUDS ʹ͓͚Δઅ఺ͷҠಈʹඞཁͳ‫্ྻހׅ‬ͷૢ࡞͸ɼo(n)Ϗοτͷิॿσʔλߏ଄ʹΑΓఆ਺࣌ؒͰ༩͑ΒΕΔ [10, 12]ɽ12___3_4_5_____6_7__8___9_0_1_2__3__4

અ఺਺ n ʹର͠ɼͦͷϝϞϦ࢖༻ྔ͸ 2n + o(n) ϏοτͰ͋Δɽ

L

2. 4 Elias-Fano ද‫ݱ‬|ide|t|a|ology|e|ie|rie|l|s|a|ch|ie|nology
12345678901234

Elias-Fano ද‫[ ݱ‬13,14] ͱ͸ɼ࠷େ஋͕ n Ͱ͋Δ m ‫ݸ‬ͷ੔਺஋͔Βߏ੒͞ΕΔ޿ٛ୯ௐ૿Ճྻʹର͠ɼఆ਺࣌ؒͰͷΞΫη

Dictionary encoding

L’F_BtaEeCFlsaACD
01001011100111

BT

10110110111011001100000011000
00001011111111nεΛอূͭͭ͠ɼ2m + m log m+ o(m) ϏοτͰද‫͢ݱ‬ΔͨΊ

12345678901234567890123456789

ͷූ߸Ͱ͋ΔɽElias-Fano ද‫ݱ‬ͷޮ཰తͳ࣮૷͸͍͔ͭ͋͘Δ
͕ɼެ։͞Ε͍ͯΔ࣮૷ͱͯ͠͸ Succinct [15] ͕༗໊Ͱ͋Δɽ

A
B
C
D
E
F

ch
ide
ie
nologyologyrie(b) C-Trie ͷද‫ݱ‬

3. จࣈྻࣙॻ

ਤ 1: S ex ʹର͢Δ C-Trieɼ‫ͼٴ‬ද‫ݱ‬ͷྫ∗จࣈྻࣙॻͱ͸ɼจࣈྻͷू߹ S ⊂ Σ Λอ؅͠ɼ֤จࣈྻ

ʹର͠‫ݻ‬༗ͷ ID ͱͯ͠ [1, |S|] ಺ͷ੔਺஋Λ༩͑ΔͨΊͷσʔλߏ଄Ͱ͋Δɽ͜ͷͱ͖ɼҎԼͷ 2 ͭͷૢ࡞Λఏ‫͢ڙ‬Δɽ

••Lookup(s)ɿs ∈ S Ͱ͋Ε͹ɼͦͷ ID Λฦ͢ɽAccess(i)ɿID i ʹରԠ͢ΔจࣈྻΛ෮‫͢ݩ‬Δɽ

·ͨɼ͋Δจࣈྻͷ‫⟨ ྻܥ‬s1 , s2 , ..., sn ⟩ ΛɼจࣈྻࣙॻΛ༻͍ͯ੔਺஋ͷ‫⟨ ྻܥ‬i1 , i2 , ..., in ⟩ ʹม‫͢׵‬Δૢ࡞Λࣙॻූ߸Խͱ

‫Ϳݺ‬ɽ‫ج‬ຊతʹɼจࣈྻΑΓ΋੔਺஋ͷํ͕֨ೲʹඞཁͳྖҬ͸খ͘͞ɼ੔਺஋ྻͱจࣈྻࣙॻͷϝϞϦ࢖༻ྔΛ଍͠߹Θͤͨ݁Ռ͕ɼ‫ݩ‬ͷจࣈྻ‫ྻܥ‬ͷϝϞϦ࢖༻ྔΑΓ΋খ͍͞৔߹ɼ
ࣙॻූ߸ԽʹΑΔѹॖ͕ୡ੒͞ΕΔɽ
ຊ‫Ͱڀݚ‬͸ɼTrie ΍ Front-Coding ಺ʹ෦෼తʹ‫ݱ‬ΕΔจࣈ
ྻʹରͯࣙ͠ॻූ߸ԽΛద༻͢Δ͜ͱͰɼ‫ط‬ଘͷࣙॻߏ଄ͷվྑΛਤΔɽͦ͜ͰຊઅͰ͸ɼCompact TrieʢC-TrieʣɼPath-

Decomposed TrieʢPD-TrieʣɼFront-Coding ͷ 3 ͭͷࣙॻߏ଄ɼ͓Αͼ‫ط‬ଘͷ࣮૷ํ๏ʹ͍ͭͯઆ໌͢ΔɽՃ͑ͯɼࣙॻූ
߸ԽΛద༻͢ΔͨΊͷσʔλߏ଄ΛఏҊ͢Δɽ

3. 1 Compact TrieʢC-Trieʣ
Trie ͱ͸ɼจࣈྻͷ‫ڞ‬௨઀಄ࣙΛซ߹͠ɼࢬʹจࣈΛ෇ਵ͢Δ
͜ͱͰߏங͞ΕΔϥϕϧ෇͖ॱং໦Ͱ͋Δɽొ࿥จࣈྻ͸ɼ͔ࠜΒ༿΁ͷ‫ܦ‬࿏্ͷࢬϥϕϧΛ࿈݁͢Δ͜ͱʹΑΓ෮‫͞ݩ‬ΕΔɽͦ
ͯ͠ɼC-Trie ͱ͸ɼTrie ʹ͓͚Δ෼‫ذ‬Λ࣋ͨͳ͍અ఺Λ࡟আ͠ɼࢬʹจࣈྻͷϥϕϧΛ༩͑Δ͜ͱʹΑΓߏங͞ΕΔ໦ߏ଄Ͱ͋Δɽ
ਤ 1a ʹɼจࣈྻू߹ S ex = {“ideal”, “ideas”, “ideology”,“tea”, “techie”, “technology”, “tie”, “trie”} ʹର͢Δ CTrie ͷྫΛࣔ͢ɽ
C-Trie Λ༻͍ͨѹॖจࣈྻࣙॻͱͯ͠஌ΒΕΔͷ͕ɼຊ‫ڀݚ‬ͷಈ‫Ͱػ‬΋͋Δɼ໼ాʹΑͬͯఏҊ͞Εͨ MARISAʢMatching

Algorithm with Recursively Implemented StorAgeʣ[5] Ͱ͋ΔɽMARISA ͱ͸ɼC-Trie ͷϥϕϧѹॖʹ C-Trie Λ༻͍Δͱ

͍͏ॲཧΛ࠶‫ؼ‬తʹ‫܁‬Γฦ͢͜ͱͰߏங͞ΕΔσʔλߏ଄Ͱ͋Δɽ͜͜Ͱ͸ MARISA ΛࢀߟʹɼC-Trie ͷѹॖʹࣙॻූ߸Խ
Λ༻͍Δํ๏Λઆ໌͢Δɽ

C-Trie ͷѹॖʹࣙॻූ߸ԽΛ༻͍Δ৔߹ɼͦͷର৅ͱͳΔͷ͸ࢬϥϕϧͰ͋ΔɽMARISA Ͱ͸ࢬϥϕϧʹؔͯ͠ɼ௕͞ 1ͷϥϕϧͱ௕͞ 2 Ҏ্ͷϥϕϧΛ۠ผ͠ɼ‫ऀޙ‬Λࣙॻූ߸ԽʹΑΓ੔਺஋ʹஔ͖‫͑׵‬ΔɽԾʹઅ఺ v ʹ޲͔͏ࢬͷϥϕϧΛ֨ೲͨ͠഑ྻΛ L[v] ͱ͢ΔͱɼL ͸഑ྻ L′ ͱϏοτྻ F Λ༻͍ͯҎԼͷΑ͏ʹஔ͖‫͑׵‬ΒΕΔɽ

••|L[v]| = 1 ͷ৔߹ɼL′ [v] ← L[v] ͔ͭ F [v] ← 0ɽ
|L[v]| >= 2 ͷ৔߹ɼจࣈྻ L[v] Λࣙॻූ߸Խ͠ಘΒΕΔ

ID Λ iv ͱ͢ΔͱɼL′ [v] ← iv ͔ͭ F [v] ← 1ɽ

ਤ 1a ͷ C-Trie ΛɼMARISA ͱಉ༷ͷํ๏Ͱࣙॻූ߸ԽʹΑΓද‫ྫͨ͠ݱ‬Λਤ 1b ʹࣔ͢ɽMARISA Ͱ͸ɼ໦ͷද‫ʹݱ‬

LOUDS Λ༻͍͍ͯΔͨΊɼL ͸ࢬϥϕϧΛ෯༏ઌॱʹฒ΂ͨ݁ՌͰ͋Γɼࣙॻූ߸ԽΛ༻͍ͯ L ͷ୅ΘΓʹ L′ ͱ F ͕ಘΒΕΔɽB ͸໦ʹର͢Δ LOUDS ද‫͋Ͱݱ‬ΓɼT ͸અ఺ v ͕จࣈྻͷऴ୺ʹҐஔ͢Ε͹ T [v] = 1 ͱͳΔΑ͏ͳϏοτྻͰ͋
ΔɽT ͸จࣈྻͷऴ୺Λද͚ͩ͢Ͱͳ͘ɼRank/Select ʹΑΓઅ఺ ID ͔Β [1, |S|] ಺ͷจࣈྻ ID ΁ͷࣸ૾Λ༩͑Δ໾ׂ΋Ռͨ͢ɽ͜ͷͱ͖ɼLookup/Access ͸ҎԼͷΑ͏ʹ࣮ߦ͞ΕΔɽ

Lookup(s) ͸ɼs Λߏ੒͢ΔจࣈʹΑΓ͔ࠜΒ༿ v ΁ભҠ͠ɼ
Rank1 (T, v) Ͱͦͷ ID Λฦ͢ɽAccess(i) ͸ɼSelect1 (T, i) ʹΑΓ෮‫͍ͨ͠ݩ‬จࣈྻͷऴ୺ʹҐஔ͢Δઅ఺ ID Λऔಘ͠ɼͦ
͔͜Βࠜ·ͰͷࢬϥϕϧΛ࿈݁͢Δ͜ͱͰొ࿥จࣈྻΛ෮‫͢ݩ‬Δɽ͜ΕΒૢ࡞ʹ͓͍ͯࢬϥϕϧΛࢀর͢Δͱ͖ɼF [v] = 1 Ͱ͋Ε͹ L′ [v] ʹ֨ೲ͞Εͨ ID Λ༻͍ͯࣙॻ͔ΒࢬϥϕϧΛਵ࣌෮‫͢ݩ‬Δɽ

i

d

e

e

ie

5

4

3

8

s

Trie ͷ෼ղʹؔͯ͠ɼͲͷࢠΛ୧Γ‫ܦ‬࿏Λબ୒͢Δ͔͸೚ҙͰ͋Δ͕ɼ͜ͷྫͰ͸ Heavy Path ͱ‫ݺ‬͹ΕΔ‫ܦ‬࿏Λબ୒ͯ͠
͍ΔɽHeavy Path ͱ͸ɼࢠͷબ୒ʹ͓͍ͯɼͦͷࢠΛࠜͱ͢
Δ෦෼໦Ͱ࠷΋ଟ͘ͷ༿Λ࣋ͭࢠΛબ୒͠ଓ͚Δ͜ͱʹΑΓಘhΒΕΔ‫ܦ‬࿏Ͱ͋ΔɽHeavy Path Λબ୒͠ Trie Λ෼ղ͢Δૢ࡞
7

6

rie
c

a

ology

a
l

֤෦෼ Trie ΁޲͔͏ࢬͷϥϕϧΛ༩͑Δɽ

tnologyie12(a) Trieɽͨͩ͠ɼ֤༿ʹ޲͏‫ܦ‬࿏্ͷ಺෦અ఺͸লུ͍ͯ͠Δɽ͸ɼҰൠʹ Centroid Path DecompositionʢCPDʣͱ‫ݺ‬͹Εɼ

CPD ʹΑΓಘΒΕΔ PD-Trie ͷߴ͞͸ߴʑO(log |S|) ͱͳΔ͜ͱ͕஌ΒΕ͍ͯΔɽ͢ͳΘͪɼCPD ͸અ఺ؒͷϥϯμϜΞ

Ϋηεͷճ਺Λ཈੍͠ɼΩϟογϡޮ཰ͷΑ͍ Trie ࣙॻΛߏங
Ͱ͖ΔɽຊߘͰ͸ CPD ʹΑΔ PD-Trie ͷߏ੒Λલఏͱ͢Δɽ

1|1t2e1ch1ien2|ology

PD-Trie ͷද‫ͯؔ͠ʹݱ‬ɼ֤અ఺ v ͸અ఺ϥϕϧΛ֨ೲͨ͠

i
a
3|

i

r

4|e

5|ie

6|de1a1l

Lv ɼઅ఺ v ͔Βग़Δ෼‫ذ‬จࣈΛ‫֨ʹॱٯ‬ೲͨ͠ Ev ɼઅ఺ v ͷ
DFUDS ද‫ ݱ‬Bv ʹΑΓද‫͞ݱ‬ΕΔɽઅ఺൪߸͸ਂ͞༏ઌॱʹ༩so͑ΒΕɼLv , Ev , Bv Λઅ఺൪߸ͷॱʹ࿈݁͢Δ͜ͱʹΑΓಘΒ

7|8|logyΕΔ഑ྻ L, E, B ʹΑΓ PD-Trie ͸ද‫͞ݱ‬ΕΔʢਤ 2cʣɽPD-(b) PD-Trieɽ֤અ఺ͷࠨ෦͸અ఺ IDɼӈ෦͸અ఺ϥϕϧΛ

Trie ʹ͍ͭͯ͸ද‫ํݱ‬๏ͷ঺հʹཹΊΔͨΊɼLookup/Accessද͍ͯ͠Δͷ࣮ߦํ๏ʹ͍ͭͯ͸‫ݪ‬ஶ࿦จ [2] Λࢀߟ͞Ε͍ͨɽ

1__________2____3_4__5_6_____7_8
LL’

1t2e1ch1ie|ology||ie|e|de1a1l||logy
12345678

Dictionary encoding

GFADCBAE

A
B
C
D
E
F
G

1234567890123456789
EB

irianos((((((()))))))(()))

de1a1l
e
ie
logy
ology
1t2e1ch1ie(c) PD-Trie ͷද‫ݱ‬ਤ 2: S ex ʹର͢Δ TrieɼPD-Trieɼ‫ͦͼٴ‬ͷද‫ݱ‬ͷྫ

3. 2. 1 ैདྷͷ࣮૷L ͸ɼΣ′ = Σ ∪ {1, 2, ..., σ − 1} ͔ΒͳΔจࣈΛཁૉͱ͠ɼ࣮ࡍ Σ = [0, 256) ͳ͜ͱ͔Β Σ′ = [0, 511) Ͱ͋Δɽ͜ͷ L ͷ࣮૷ʹؔͯ͠ɼจ‫[ ݙ‬2] Ͱ͸ 2 ͭͷख๏ΛఏҊ͍ͯ͠Δɽ

1 ͭ͸ɼL Λ Vbyte [16] ʹΑΓόΠτྻʹஔ͖‫͑׵‬Δ୯७ͳ
ख๏Ͱ͋Δɽ͜ͷͱ͖ɼΣ′ ͷ֤஋Λ L ʹ͓͍ͯग़‫ݱ‬ස౓͕େ͖͍ॱʹ 0 ͔ΒׂΓৼΔ͜ͱͰɼੜ੒͞ΕΔόΠτྻΛখ͘͞
͢Δ͜ͱ͕Ͱ͖Δʢ஫ 1ʣɽ΋͏ 1 ͭ͸ɼL Λ Re-Pair [9] ʹΑΓѹॖ͢Δख๏Ͱ͋Δɽͨͩ͠ɼΦϦδφϧͷ Re-Pair ͷ࣮૷Ͱ
͸ͳ͘ɼApproximate Re-Pair [17] ʹमਖ਼ΛՃ࣮͑ͨ૷Λద༻
͍ͯ͠Δɽ͜ͷ࣮૷Ͱ͸ɼ͋Δఔ౓ͷѹॖ཰Λ٘ਜ਼ʹɼѹॖίετͱ෮‫ݩ‬ίετΛҰఆʹ཈͑Δ͜ͱ͕Ͱ͖Δɽ·ͨɼͲͪΒ

3. 2 Path-Decomposed TrieʢPD-Trieʣ
PD-Trie ͱ͸ɼTrie Λઅ఺͔Β༿·Ͱͷ‫ܦ‬࿏ʹ෼ղ͢Δૢ࡞ʢPath DecomposionʣΛ࠶‫ؼ‬తʹ‫܁‬Γฦ͢͜ͱʹΑΓߏங͞Ε
Δ໦ߏ଄Ͱ͋Γɼ֤અ఺͕֤‫ܦ‬࿏ʹରԠ͢Δɽ͜͜Ͱ͸ɼ·ͣॳΊʹɼਤ 2 ʹࣔ͢ྫΛ༻͍ͯ Grossi ͱ Ottaviano [2] ʹΑΔจࣈྻࣙॻʹ‫ ͮ͘ج‬PD-Trie ͷσʔλߏ଄ɼ‫ैͼٴ‬དྷͷ࣮૷ํ๏Λઆ໌͢Δɽ࣍ʹɼࣙॻූ߸ԽΛѹॖʹద༻͢ΔͨΊͷσʔλߏ଄ʹ͍ͭͯఏҊ͢Δɽ
ਤ 2b ʹࣔ͢໦ߏ଄͸ɼਤ 2a ͷ Trie Λ࣮ઢͰ‫͕ܨ‬Εͨ‫ܦ‬࿏͝ͱʹ෼ղ͠ߏங͞Εͨ PD-Trie Ͱ͋Γɼ֤અ఺ʹ͸ Trie ͷ֤‫ܦ‬࿏Λද͢અ఺ϥϕϧɼ֤ࢬʹ͸෼‫ذ‬จࣈ͕෇ਵ͍ͯ͠Δɽ
અ఺ϥϕϧʹ‫·ؚ‬ΕΔ 1, 2, ... ͱ͍͏จࣈ͸ Σ ʹ‫·ؚ‬Εͳ͍ಛघจࣈͰ͋Γɼ෼‫͕͋ذ‬ΔՕॴͱ෼‫਺ذ‬Λ͍ࣔͯ͠Δɽ͜͏ͨ͠ PD-Trie ͸ҎԼͷखॱͰߏங͞ΕΔɽ·ͣɼTrie ͷ͔ࠜΒ೚ҙͷ༿·Ͱͷ‫ܦ‬࿏ π Λબ୒͢Δɽ࣍ʹɼ‫ܦ‬࿏ π ্ͷࢬͷจͷख๏ʹରͯ͠΋ɼL ʹ͓͚Δઅ఺ϥϕϧͷ‫ڥ‬ք͸ Elias-Fanoද‫ݱ‬Λ༻͍ͯ‫ه‬Ա͓ͯ͘͠ɽ

3. 2. 2 ࣙॻූ߸ԽΛ༻͍ͨѹॖࣙॻූ߸ԽΛ༻͍ͨ PD-Trie ͷѹॖͰ͸ɼL ʹ‫·ؚ‬ΕΔ֤અ
఺ϥϕϧʢۭจࣈྻ΋‫ؚ‬Ήʣʹରࣙ͠ॻූ߸ԽΛద༻͢Δɽਤ

2c ͷ L′ ͸ɼL ͷ֤અ఺ϥϕϧΛࣙॻූ߸Խ͠ɼID ʹஔ͖‫͑׵‬ͨ݁ՌͰ͋Δɽ͜ͷͱ͖ɼઅ఺ϥϕϧ͸ Vbyte ʹΑΓόΠτྻʹม‫߸ූॻࣙ͠׵‬ԽΛద༻͢ΔɽL′ ͸୯ͳΔ੔਺஋ྻʹͳΔͨ
Ίɼ୯७ͳ‫ݻ‬ఆ௕഑ྻͱͯ͠؅ཧͰ͖ɼ֤અ఺ϥϕϧͷ‫ڥ‬քΛ‫ه‬Ա͢Δඞཁ͸ͳ͘ͳΔɽ

3. 3 Front-Coding
Front-Coding ͱ͸ɼࣙॻࣜॱʹ੔ྻ͞Εͨจࣈྻू߹ʹର͠ɼ֤จࣈྻΛͦͷ௚લͷจࣈྻͱͷ࠷௕‫ڞ‬௨઀಄ࣙ௕ͱɼ࢒ͬ
ͨ઀ඌࣙͷϖΞʹූ߸Խ͢Δٕ๏Ͱ͋Δɽࣗવ‫ޠݴ‬΍ URL ͳͲɼ࣮ࡍͷίʔύεʹ͸ࣅͨΑ͏ͳ઀಄͕ࣙଟ͘‫ݱ‬ΕΔͱ͍͏

ࣈͱɼ֤અ఺ʹ͓͍ͯ෦෼ Trie ͕ਨΕԼ͕͍ͬͯΔ৔߹ʹ͸ɼಛ௃Λར༻͠ѹॖ͢Δɽࣙॻͱ֤ͯ͠จࣈྻʹϥϯμϜΞΫη

ͦͷ෦෼ Trie ͷ਺Λࣔ͢ಛघจࣈ ∈ {1, 2, ...} ͱΛ࿈݁͢Δ͜

ε͍ͨ͠৔߹ʹ͸ɼจࣈྻू߹ΛҰఆ‫਺ݸ‬ͷจࣈྻ͔ΒͳΔόͱͰಘΒΕΔจࣈྻΛɼPD-Trie ͷࠜ vπ ͷઅ఺ϥϕϧͱ͢Δɽࠜ vπ ͷࢠ͸ɼ‫ܦ‬࿏ π ͔ΒਨΕԼ͕Δ෦෼ Trie ʹର͢Δ PDT
ͷࠜͱͯ͠࠶‫ؼ‬తʹఆٛ͢Δɽ͜ͷͱ͖ɼࢠ΁ͷ෼‫ذ‬จࣈʹ͸ʢ஫ 1ʣɿจ‫[ ݙ‬2] ͷ࣮૷Ͱ͸ɼӳจʹର͠େ൒ͷจࣈ͕ [0, 128) ಺ͷ஋ΛऔΔ͜
ͱΛલఏͱ͍ͯ͠ΔͨΊɼ͜ͷΑ͏ͳ޻෉͸ࢪ͍ͯ͠ͳ͍ɽ

idealideas
ideologyteatechietechnology
tie
trie

FrontCoding

ideal$techie$
17430411ECFBADਤ 3: Sex

อ؅͢ΔͨΊʹ༻͍ΒΕΔɽͨͩ͠ɼຊ༻్Ͱ͸ิॿจࣈྻࣙ
ॻ͕จࣈྻʹׂΓ౰ͯΔ ID ʹ͍ͭͯɼͦͷ஋ҬΛ੍‫͍ͳ͠ݶ‬ɽ
Dictionary encoding
A
B
C
D
E
F

ideal
4 E
3 C
0 F
techie
4 B
1 A
1 D

1234567890123
H
P
C
L಺ʹ࢒ΔจࣈྻΛ੔਺஋ʹஔ͖‫͑׵‬ɼͦΕΒจࣈྻΛผྖҬͰ

ideal
4 s
3 ology0 teatechie4 nology
1 ie
1 rie

ie
nology
ology
rie
s
tea

Lookup/Access ʹ͓͍ͯจࣈྻΛ෮‫͢ݩ‬Δ༻్Ͱ༻͍ΒΕΔิॿจࣈྻࣙॻʹ͍ͭͯɼఏ‫࡞ૢ͖΂͢ڙ‬ΛҎԼʹఆٛ͢Δɽ

••Restore(i)ɿID i ʹରԠ͢ΔจࣈྻΛ෮‫͢ݩ‬Δɽ
Compare(i, q)ɿRestore(i) ͱΫΤϦจࣈྻ q Λൺֱ͢Δɽ

Restore ͸ Access ͱಉ༷ͷૢ࡞͕ͩɼද‫ه‬ͷࠞಉΛආ͚ΔͨΊʹվΊͯఆٛͨ͠ɽCompare ͸ Lookup ʹ͓͍ͯ‫ͼݺ‬ग़͞ΕΔૢ࡞Ͱ͋ΔɽRestore ͕࣮ߦͰ͖Ε͹ Compare ΋࣮ߦͰ͖Δ͕ɼRestore ͸෮‫͢ݩ‬ΔจࣈྻΛඞͣ࠷‫Ͱ·ޙ‬ಡΈࠐΉʹର͢Δ Front-Coding ͷྫͷʹର͠ɼCompare ͸ΫΤϦͱϛεϚονͯ͠Δ৔߹ɼ࠷‫·ޙ‬ͰಡΈࠐΉඞཁ͸ͳ͍ɽέοτʹ෼ׂ͠ɼόέοτͷ࠷ॳͷจࣈྻʢϔομʔʣΛූ߸ຊઅͰ͸ɼҎԼͷ͜ͱΛߟྀ͠ิॿจࣈྻࣙॻΛఏҊ͢Δɽ

Խͤͣʹͦͷ··֨ೲ͓ͯ͘͠ɽ͜ͷͱ͖ɼจࣈྻͷ ID ͸ࣙ•ॻࣜॱʹׂΓৼΒΕΔɽਤ 3 ͷ্෦͸ɼόέοτͷαΠζΛ 4
ͱͯ͠ S

ex

ʹ Front-Coding Λద༻ͨ͠৔߹ͷྫΛ͍ࣔͯ͠Δɽ

Lookup ͸ɼϔομʔʹର͢Δೋ෼୳ࡧʹΑΓɼͦͷจࣈྻ͕Ұճͷ Lookup ·ͨ͸ Access ʹ͓͍ͯɼCompare ·ͨ͸ Restore ͸ෳ਺ճ‫ͼݺ‬ग़͞ΕΔɽͦͷͨΊɼจࣈྻࣙॻҎ্ʹ࣮ߦ͕࣌ؒॏཁࢹ͞ΕΔɽ

•Trie ΍ Front-Coding ʹΑͬͯɼ઀಄͕ࣙ‫ڞ‬༗͞Εߏங‫·ؚ‬Ε͍ͯΔόέοτΛಛఆ͠ɼͦͷதΛஞ࣍తʹௐ΂Δ͜ͱ͞Εͨࣙॻ಺ʹ࢒Δ෦෼จࣈྻΛอ؅ͷର৅ͱ͢Δɽ͜ΕΒͷͰ࣮ߦ͞ΕΔɽAccess ͸ɼड͚औͬͨ ID ͔Βόέοτͱɼͦจࣈྻʹ͸ɼࣅͨΑ͏ͳ઀ඌ͕ࣙଟ͘‫ݱ‬ΕΔ͜ͱ͕༧૝͞ΕΔɽ

ͷόέοτ಺ͰͷΦϑηοτࢉग़͠ɼϔομʔ͔Βॱʹ෮‫͠ݩ‬

4. 1 ୯७ͳ઀ඌࣙซ߹

͍ͯ͘͜ͱͰ࣮ߦ͞ΕΔɽ

ิॿจࣈྻࣙॻΛ࣮‫͢ݱ‬Δ࠷΋୯७ͳσʔλߏ଄͸ɼऴ୺จ

3. 3. 1 ैདྷͷ࣮૷ࣈΛ෇༩ͨ͠จࣈྻΛϝϞϦ্ʹ࿈ଓͯ͠഑ஔ͠ɼ֤จࣈྻͷ

Front-Coding Λ༻͍ͨࣙॻͷ୯७ͳ࣮૷ͱͯ͠͸ɼ[1] Ͱఏઌ಄ҐஔΛ ID ͱͯ͠ಘΔख๏Ͱ͋Δɽ͜ͷͱ͖ɼ͋ΔจࣈྻҊ͞Εͨ Plain Front-CodingʢPFCʣ͕͋͛ΒΕΔɽPFC ͸ɼ͕ଞͷจࣈྻͷ઀ඌࣙʹ‫·ؚ‬ΕΔ৔߹ɼͦΕΒΛซ߹͢Δ͜ͱ

ऴ୺จࣈ͕෇༩͞ΕͨจࣈྻͱɼVbyte ʹΑΓόΠτྻʹஔ͖͕Ͱ͖Δɽ͜͏ͯ͠ߏங͞ΕΔ഑ྻ͸Ұൠʹ TAIL ͱ‫ݺ‬͹Ε‫͑׵‬ΒΕͨ‫ڞ‬௨઀಄ࣙ௕ΛɼϝϞϦ্ʹ࿈ଓͯ͠഑ஔ͠ɼ֤ϔοΔ [4, 5]ɽ‫ ࣔ͢ʹޙ‬Reverse Trie ΍ Back-Coding ͱൺ΂Δͱɼμʔͷઌ಄ҐஔΛ‫ه‬Ա͓ͯ͘͠σʔλߏ଄Ͱ͋Δɽ·ͨ [1] Ͱ͸ɼซ߹Ͱ͖Δจࣈྻͷׂ߹͸গͳ͍͕ɼ୯७ͳจࣈྻͱͯ͠ߴ଎

ೋ෼୳ࡧͷର৅ͱͳΔϔομʔҎ֎ͷόΠτྻʹର͠ Re-PairʹࢀরͰ͖Δɽʢ஫ 2ʣΛద༻͢Δ͜ͱͰɼPFC Λѹॖ͍ͯ͠ΔɽఏҊऀͷ࣮૷Ͱ

4. 2 Reverse Trie͸ɼNavarro ʹΑΓެ։͞Ε͍ͯΔΦϦδφϧʹ͍ۙ Re-PairຊߘͰ͸ɼจࣈྻΛ‫͔ํޙ‬Βซ߹͢Δ͜ͱʹΑͬͯߏங͞Ε࣮૷ʢhttps://www.dcc.uchile.cl/~gnavarro/software/ʣ

Δ Trie Λ Reverse Trie ͱ‫Ϳݺ‬ɽReverse Trie Ͱ͸ɼจࣈྻͷΛ࠾༻͍ͯ͠Δɽ

ऴ୺͕ࠜʹରԠ͠ɼ༿͔Βࠜͷํ޲ʹ୧Δ͜ͱͰొ࿥จࣈྻ͕

3. 3. 2 ࣙॻූ߸ԽΛ༻͍ͨѹॖ෮‫͖Ͱݩ‬Δɽ͢ͳΘͪɼจࣈྻͷ࢝఺ͱͳΔઅ఺ ID Λอ࣋ࣙ͠ॻූ߸ԽΛ༻͍ͨ Front-Coding ͷѹॖͰ͸ɼPFC ͷѹॖ͓ͯ͘͜ͱͰɼRestore ΍ Compare ͕࣮ߦͰ͖Δɽ͜͜Ͱ͸ɼͱಉ͘͡ϔομʔҎ֎ͷจࣈྻΛࣙॻූ߸ԽʹΑΓ ID ʹஔ͖

Compact Trie Λ༻͍ͨ Reverse Trie ͷ࣮૷Ͱ͋Δ Reverse‫͑׵‬Δɽਤ 3 ͷԼ෦ʹͦͷྫΛࣔ͢ɽຊఏҊʹ͓͚Δ Front-

Compact TrieʢRC-TrieʣͱɼPD-Trie Λ༻͍࣮ͨ૷Ͱ͋Δ

Coding ࣙॻ͸ɼϔομʔจࣈྻΛ֨ೲ͢ΔͨΊͷ഑ྻ H ͱɼ

Reverse Path-Decomposed TrieʢRPD-Trieʣͷ 2 छྨͷσʔϔομʔͷ֤ઌ಄ҐஔΛࣔ͢ϙΠϯλͷ഑ྻ P ɼ‫ڞ‬௨઀಄ࣙ௕

λߏ଄͍ͭͯઆ໌͢ΔɽRC-Trie ͸ɼMARISA ͷิॿจࣈྻΛ֨ೲ͢Δ഑ྻ C ɼࣙॻූ߸ԽʹΑΓಘΒΕͨ ID Λ֨ೲ͢Δ

ࣙॻͱͯ͠༻͍ΒΕ͍ͯΔ‫ط‬ଘͷ࣮૷ख๏Ͱ͋ΔɽRPD-Trie഑ྻ L ʹΑΓߏ੒͞ΕΔɽ

͸ɼຊߘͰ৽ͨʹఏҊ͢Δσʔλߏ଄Ͱ͋ΓɼRC-Trie ΑΓ΋

4. จࣈྻࣙॻѹॖͷͨΊͷจࣈྻࣙॻ

ߋʹߴ଎ͳ෮‫ݩ‬Λఏ‫͢ڙ‬Δิॿจࣈྻࣙॻͷ࣮૷Ͱ͋Δɽ

4. 2. 1 Reverse Compact TrieʢRC-Trieʣද‫ه‬ͷࠞಉΛආ͚ΔͨΊɼจࣈྻࣙॻͷѹॖΛ໨తͱͯ͠༻

RC-Trie ͸ɼઅ 3. 1 Ͱઆ໌ͨ͠ํ๏ͱಉ༷ͷ࣮૷ͰɼReverse͍ΒΕΔจࣈྻࣙॻΛɼຊߘͰ͸ิॿจࣈྻࣙॻͱ‫Ϳݺ‬ɽิॿ

Trie ʹΑΔࣙॻΛ࣮‫͢ݱ‬Δɽͨͩ͠ɼ֤અ఺ ID Λจࣈྻͷ ID

จࣈྻࣙॻ͸ɼઅ 3. Ͱ঺հͨ͠Α͏ʹɼTrie ΍ Front-Codingͱͯ͠༩͑ɼ͔ͦ͜Βࠜʹ޲͔ͬͯ୧Δ͜ͱͰจࣈྻΛ෮‫ݩ‬͢ΔͨΊɼ֤จࣈྻͷऴ୺Λද͢Ϗοτྻ T ͸ඞཁͱ͠ͳ͍ɽ

ʢ஫ 2ʣɿจ‫[ ݙ‬1] Ͱ͸ɼଞʹ΋ Hu-Tucker ූ߸ [7] Λ༻͍ͨϔομʔͷѹॖ΋ఏҊ͍ͯ͠Δ͕ɼຊߘͰ͸ϔομʔҎ֎ͷจࣈྻʹର͠ɼRe-Pair Λద༻ͨ͠৔

RC-Trie ΋·ͨɼࣙॻූ߸ԽʹΑΓѹॖ͞ΕΔσʔλߏ଄Ͱ͋߹ͱࣙॻූ߸ԽΛద༻ͨ͠৔߹ͱͷൺֱΛ໨తͱ͍ͯ͠ΔͨΊɼϔομʔͷѹॖΔɽMARISA Ͱ͸༧ΊܾΊͨ਺ͷ෼͚ͩ RC-Trie Λ࠶‫ؼ‬తʹʹ͍ͭͯ͸ධՁ͍ͯ͠ͳ͍ɽ

ߏங͠ɼ࠷‫࢒ʹޙ‬Δจࣈྻ͸ TAIL ʹΑΓอ؅͢Δɽnͱͨ͠ͱ͖ɼP ͸ 2m + m log m+ o(m) Ϗοτཁ͢Δɽ؆ܿ$໦ʹΑΓ Reverse Trie Λද‫͢ݱ‬Δ৔߹ɼͦͷϝϞϦ࢖༻ྔ͸

y

e
d

h

1|$eir

i
C

i

h

o

c
r

B

n
2n + n log σ + o(n) ϏοτͰ͋Γɼ͓͓Αͦ 2m + m log m
<n

g

A
l

F

2|c

n
D
(a) Reverse Trieͷͱ͖ɼRPD-Trie ͸؆ܿ໦ද‫ݱ‬ΑΓখ͘͞ͳΔɽ͜͜Ͱɼmd

3|golon4|i__CF_A____ED_B
12345678901234

o
E

y

L
B
P

$eirhcygolondi
00001010000010
112(b) RPD-Trieਤ 4: Reverse Trie ͱ RPD-Trie ͷྫ͸ Reverse Trie ͷ༿ͷ਺͔Β 1 ΛҾ͍ͨ஋Ͱ͋Γɼਤ 4 ͷྫʹ΋‫ݟ‬ΒΕΔΑ͏ʹɼn ͱൺ΂Δͱ࣮ࡍʹ͸͔ͳΓখ͍͞஋ͱ
ͳΔɽͦͷͨΊɼRPD-Trie ͸؆ܿ໦ͱಉ౳ɼ΋͘͠͸ͦΕҎ্ͷϝϞϦޮ཰͕‫ظ‬଴Ͱ͖ɼ͔ͭΩϟογϡޮ཰ͷྑ͍෮‫ݩ‬Λఏ‫͖Ͱڙ‬Δɽ

4. 3 Back-Coding
Front-Coding ͷٕ๏Λɼ઀ඌࣙʹର͠ద༻͢Δ͜ͱͰิॿ
จࣈྻࣙॻΛ࣮‫͢ݱ‬ΔɽຊߘͰ͸ɼ͜ͷٕ๏Λ Back-Coding ͱ‫Ϳݺ‬ɽBack-Coding Ͱ΋ Front-Coding ͱಉ༷ʹɼจࣈྻू߹

4. 2. 2 Reverse Path-Decomposed TrieʢRPD-TrieʣΛόέοτʹ෼ׂ͠ϔομʔ͔Βॱʹ෮‫͢ݩ‬Δɽิॿจࣈྻࣙ

RC-Trie ΑΓ΋ߴ଎ͳ Reverse Trie ͷ࣮૷Λߟ͑Δ৔߹ɼॻͰ͸ߴ଎ੑ͕‫ٻ͘ڧ‬ΊΒΕΔͨΊɼຊ‫Ͱڀݚ‬͸ Back-CodingΩϟογϡޮ཰ΛߴΊΔ Path Decomposion ͷར༻͕༗ྗͳબ

Λ୯७ʹ PFC ʹΑΓ࣮૷͢Δɽ

୒ࢶͱͳΔ͕ɼจ‫[ ݙ‬2] ͷ࣮૷Ͱ͸ɼ֤અ఺ϥϕϧΛઌ಄͔Β·ͨɼߋʹߴ଎ੑΛ௥‫͢ٻ‬ΔͨΊɼ௚લͱͷจࣈྻͷࠩҟͰಡΈࠐΜͰ͍͘ඞཁ͕͋ΔͨΊɼCompare ʹ͓͚ΔϛεϚο

͸ͳ͘ɼ֤όέοτ͝ͱʹϔομʔͱͷࠩҟΛ༻͍ͯஔ͖‫͑׵‬νΛଈ࠲ʹ‫ݕ‬ग़Ͱ͖ͳ͍ɽͦ͜ͰɼิॿจࣈྻࣙॻͷͨΊͷΔํ๏ [18] ΋ิॿจࣈྻࣙॻʹద༻͢ΔɽຊߘͰ͸ɼ͜ͷٕ๏PD-Trie ͷ࣮૷ɼRPD-Trie ΛҎԼʹఏҊ͢ΔɽΛ Fast Back-CodingʢFBCʣͱ‫Ϳݺ‬ɽFBC ʹΑΔࣙॻͰ͸ɼิॿจࣈྻࣙॻͷͨΊͷ Reverse Trie Ͱ͸ɼࢠΛಛఆ͢Δ

్தͷจࣈྻΛ෮‫͢ݩ‬Δඞཁ͕ͳ͘ɼϝϞϦΛίϐʔ͢Δճ਺ૢ࡞Λඞཁͱ͠ͳ͍ͨΊɼRPD-Trie ͷ࣮૷͸จ‫[ ݙ‬2] ͷ࣮૷͕ߴʑ2 ճͰࡁΉɽͨͩ͠ɼ੔਺஋ʹஔ͖‫͑׵‬ΒΕΔจࣈྻ͕ͱൺ΂୯७Ͱ͋Δɽਤ 1b Ͱ༻͍ΒΕ͍ͯΔิॿจࣈྻࣙॻগͳ͘ͳΔ෼ɼϝϞϦޮ཰ͱͷτϨʔυΦϑͱͳΔɽ

Λ Reverse Trie ʹΑΓ࣮‫ྫͨ͠ݱ‬Λਤ 4a ʹɼͦΕʹର͢Δ

RPD-Trie ͷྫΛਤ 4b ʹࣔ͢ɽઆ໌ͷ౎߹্ɼReverse Trie ʹ

5. ࣮‫ʹݧ‬ΑΔධՁ

͸ऴ୺จࣈ ‘$’ ʹΑΓεʔύʔϧʔτΛ෇༩͍ͯ͠Δɽਤ 4b ͷຊઅͰ͸ɼઅ 3. Ͱ঺հͨ͠จࣈྻࣙॻʹର͠ɼઅ 4. Ͱ঺հ

RPD-Trie ͸ɼReverse Trie ʹ CPD Λద༻͠ɼ෯༏ઌॱʹઅͨ͠ิॿจࣈྻࣙॻʹΑΔѹॖΛద༻ͨ͠৔߹ͷੑೳʹؔͯ͠఺ ID ΛׂΓ౰ͯΔ͜ͱʹΑΓߏங͞Ε͍ͯΔɽࢠΛಛఆ͢Δ

ධՁΛ༩͑Δɽඞཁ͕ͳ͍ͨΊɼ෼‫ذ‬৘ใΛࣔ͢ಛघจࣈ 1, 2, ... ͸‫·ؚ‬Εͯ

5. 1 ࣮ ‫ ݧ‬ઃ ఆ͍ͳ͍ɽ࣮‫ػࢉܭ͍ͨ༻ʹݧ‬ͷߏ੒͸ɼIntel Core i7 4.0 GHz CPUɼ

RPD-Trie ͷද‫ʹݱ‬͸ɼ3 ͭͷ഑ྻ L, B, P Λ༻͍ΔɽL ͸ɼ

16 GB RAM (L2 cache 256 KB, L3 cache 8 MB) Ͱ͋ΓɼOS

RPD-Trie ͷ֤અ఺ʹରͯ͠ɼͦͷઅ఺΁޲͔͏෼‫ذ‬จࣈʢεʔ͸ OS X 10.12 Ͱ͋Δɽࣙॻͷ࣮૷‫ޠݴ‬͸ C++Ͱɼ࠷దԽ

ύʔϧʔτҎ֎ʣͱઅ఺ϥϕϧΛ࿈݁͢Δ͜ͱʹΑΓಘΒΕΔ

Φϓγϣϯͱͯ͠-O3 Λࢦఆ͠ɼApple LLVM version 8.0.0จࣈྻΛɼઅ఺ ID ॱʹ࿈݁͢Δ͜ͱʹΑΓಘΒΕΔจࣈྻͰ(clang-800.0.42.1) Λ༻͍ͯίϯύΠϧͨ͠ɽ࣮ߦ࣌ؒͷ‫ܭ‬ଌ͋ΔɽB ͸ɼL[i] ͕෼‫ذ‬จࣈͳΒ B[i] = 1ɼઅ఺ϥϕϧͳΒʹ͸ɼstd::chrono::duration cast Λ༻͍ͨɽB[i] = 0 Ͱ͋ΔΑ͏ͳϏοτྻͰ͋ΔɽP ͸ɼ֤ࢬ͕અ఺ϥϕ

5. 1. 1 σʔλߏ଄ϧͷͲͷҐஔ͔Β෼‫͔͖ͨͯ͠ذ‬Λࣔ͢੔਺஋ྻͰ͋ΓɼL ্

C-TrieɼPD-TrieɼFront-Coding Λϕʔεͱ͢ΔจࣈྻࣙͷఴࣈΛઅ఺ ID ॱʹ֨ೲ͢ΔɽRPD-Trie ͸ɼ֤จࣈྻͷ࢝ॻʹର͠ɼTAILɼRC-TrieɼRPD-TrieɼBack-CodingɼFBC఺ʹҐஔ͢Δ L ্ͷఴࣈΛจࣈྻͷ ID ͱͯ͠ൃߦ͢Δɽ͜ͷ

ͷ 5 छྨͷิॿจࣈྻࣙॻʹΑΔѹॖΛͦΕͧΕద༻ͨ͠ɽ

ͱ͖ɼRPD-Trie ͷ Restore(i) ͸ҎԼͷखॱͰ࣮ߦ͞ΕΔɽ

RC-Trie ʹؔͯ͠ɼ1 ͭͷ RC-Trie ͱ TAIL ʹΑΓߏ੒͞Ε

ʢ 1 ʣ str Λ “” Ͱॳ‫ظ‬Խ͢Δɽ

Δࣙॻͱɼ2 ͭͷ RC-Trie ͱ TAIL ʹΑΓߏ੒͞ΕΔࣙॻΛ

ʢ 2 ʣ L[i] = ‘$’ ͳΒ str Λฦ͠ऴྃ͢Δɽ

ධՁͨ͠ʢͦΕͧΕ RCT1ɼRCT2 ͱද‫ه‬ʣɽBack-Coding ͱʢ 3 ʣ str ͷ຤ඌʹ L[i] ΛՃ͑Δɽ

FBC ͷόέοταΠζʹؔͯ͠͸ɼ4ɼ8ɼ16 ͷ 3 छྨΛධՁ

ʢ 4 ʣ B[i] = 1 ͳΒ i ← P [Rank1 (B, i)]ɼB[i] = 0 ͳΒ i Λͨ͠ʢͦΕͧΕ BC4ɼBC8ɼBC16ɼFBC4ɼFBC8ɼFBC16ϝϞϦ࢖༻ྔʹؔͯ͠ɼReverse Trie ͷઅ఺਺Λ n ͱͨ͠৔จࣈྻࣙॻɼRPD-TrieɼBack-CodingɼFBC ͕ఏҊ͞ΕͨิσΫϦϝϯτ͢Δ͜ͱͰࢀরҐஔΛߋ৽͠ɼ2 ΁໭Δɽ߹ɼL ͸ n log σ ϏοτɼB ͸ n + o(n) Ϗοτཁ͢ΔɽP ͸੔ͱද‫ه‬ʣɽҐஔ෇͚ͱͯ͠͸ɼTAIL ͱ RC-Trie ͕‫ط‬ଘͷิॿॿจࣈྻࣙॻͱͳΔɽ

਺஋ྻ͕ͩɼ෯༏ઌʹઅ఺൪߸ΛׂΓ౰ͯΔ͜ͱͰ޿ٛ୯ௐ૿

PD-TrieɼFront-Coding ʹؔͯ͠͸ɼิॿจࣈྻࣙॻΛ༻͍ՃྻͱͳΔͷͰɼElias-Fano ද‫͕ݱ‬ద༻Ͱ͖ΔɽԾʹ |P | = mͳ͍ैདྷͷ࣮૷ख๏΋ൺֱʹ༻͍ͨɽPD-Trie Ͱ͸ɼઅ఺ϥϕϧͷද‫ ʹݱ‬Vbyte ͱ Re-Pair Λ༻͍Δ 2 ͭͷ࣮૷ΛධՁͨ͠ද 1: ίʔύεʹؔ͢Δ৘ใαΠζද 2: ࣙॻ಺ʹ‫ݱ‬ΕΔจࣈྻʹؔ͢Δ৘ใ

จࣈྻ਺ ฏ‫ۉ‬௕

SW

227.2 11,519,354

20.7 199

SI

612.9

86.7

SU

7,414,866

2,723.3 39,459,925(a) SWσ
98

72.4 103αΠζ จࣈྻ਺-લ

90.9

11,580,413

3,027,555

12.8

PD-Trie

90.3

11,519,354

3,762,732

14.4

Front-Coding

83.0

10,079,434

2,921,168

13.5

ʢͦΕͧΕ PlainɼRe-Pair ͱද‫ه‬ʣɽFront-Coding Ͱ͸ɼPFC(b) SIͱͦΕʹ Re-Pair Λద༻ͨ͠ 2 ͭͷ࣮૷ΛධՁͨ͠ʢಉ͘͡

PlainɼRe-Pair ͱද‫ه‬ʣɽRe-Pair ͷ࣮૷͸ѥछ‫ؚ‬Ί͍͔ͭ͘
ଘࡏ͢Δ͕ɼຊ࣮‫Ͱݧ‬͸અ 3. Ͱ঺հͨ͠Α͏ʹɼͦΕͧΕͷఏҊऀ͕ࣙॻͷѹॖʹద༻͍ͯ͠Δ Re-Pair ͷ࣮૷Λ༻͍ͯɼจࣈྻ਺-‫ ޙ‬ฏ‫ۉ‬௕C-TrieαΠζ จࣈྻ਺-લ

จࣈྻ਺-‫ ޙ‬ฏ‫ۉ‬௕C-Trie135.8

6,472,460

1,251,149

39.1

PD-Trie134.6

7,414,866

1,300,192

44.7

Front-Coding

121.6

6,488,007

1,204,600

42.5

ϕʔεϥΠϯͱͨ͠ɽ·ͨɼFront-Coding ࣙॻͷόέοτα
Πζ͸ɼա‫ڈ‬ͷ࣮‫ݧ‬Λࢀߟʹ 8 Ͱ౷Ұͨ͠ɽ(c) SU

5. 1. 2 ί ʔ ύ εαΠζ จࣈྻ਺-લ

จࣈྻ਺-‫ ޙ‬ฏ‫ۉ‬௕ࣙॻͷߏஙʹ͸ɼҎԼͷ 3 ͭͷίʔύεΛར༻ͨ͠ɽ

C-Trie663.3

41,001,910

11,396,164

32.5

•

SW ɿӳ‫ޠ‬൛ Wikipedia ͷ‫ݟ‬ग़͠ू߹ʢhttps://dumps.

PD-Trie

655.4

39,459,925

11,958,074

35.2

Front-Coding

591.7

34,527,434

10,756,301

34.2

•

SI ɿΠϯυγφॾࠃͷυϝΠϯ্ͰΫϩʔϧ͠ಘΒ

wikimedia.org/enwiki/ʣΕ ͨ URL ू ߹ʢhttp://data.law.di.unimi.it/webdata/indochina-2004/indochina-2004.urls.gzʣ
•SU ɿ.uk υϝΠϯ্ͰΫϩʔϧ͠ಘΒΕͨ URL ू߹ʢhttp://data.law.di.unimi.it/webdata/uk-2005/uk-2005.

urls.gzʣද 1 ʹίʔύεͷ‫ج‬ຊతͳσʔλΛࣔ͢ɽʮαΠζʯ͸ੜσʔλͷαΠζɼ͢ͳΘͪจࣈྻͷ߹‫ܭ‬௕Λ͓ࣔͯ͠Γɼ୯Ґ͸

MiB Ͱ͋Δɽ
ʮจࣈྻ਺ʯ͸ɼίʔύε಺ͷॏෳΛআ͍ͨจࣈྻͷ਺ɼʮฏ‫ۉ‬௕ʯ͸ͦΕΒͷฏ‫ۉ‬จࣈ਺Λ͍ࣔͯ͠Δɽʮσ ʯ͸ɼ
ίʔύεʹ͓͍ͯ༻͍ΒΕ͍ͯΔจࣈͷछྨͷ਺Λ͍ࣔͯ͠Δɽ·ͨɼ͜ΕΒίʔύε͔Β C-TrieɼPD-TrieɼFront-CodingʹΑͬͯࣙॻΛߏஙͨ͠৔߹ʹɼࣙॻූ߸Խͷର৅ͱͯ͠‫ݱ‬ΕΔจࣈྻʹؔ͢Δ৘ใΛද 2 ʹࣔ͢ɽʮαΠζʯ͸‫ݱ‬Εͨจࣈྻͷ߹‫ܭ‬௕Λ MiB Ͱ͓ࣔͯ͠Γɼʮจࣈྻ਺-લʯ͸ͦͷจࣈྻ਺Λ͍ࣔͯ͠Δɽ
ʮจࣈྻ਺-‫ޙ‬ʯ͸͔ͦ͜ΒॏෳΛআ͍ͨ৔߹
ͷจࣈྻ਺Λ͓ࣔͯ͠Γɼʮฏ‫ۉ‬௕ʯ͸ͦͷฏ‫ۉ‬จࣈ਺Λࣔͯ͠
͍Δɽද 2 ͔Β෼͔ΔΑ͏ʹɼॏෳΛআ͚ͩ͘Ͱ΋จࣈྻ਺Λ

18–33%ʹ࡟‫͢ݮ‬Δ͜ͱ͕Ͱ͖Δɽ
5. 2 ݁ՌͱධՁ
ද 3 ʹ࣮‫݁ݧ‬ՌΛࣔ͢ɽ֤ྻͷ߲໨ʹ͍ͭͯɼʮߏங࣌ؒʯ
͸ࣙॻͷߏஙʹཁͨ࣌ؒ͠Ͱ୯Ґ͸ඵɼʮѹॖ཰ʯ͸ίʔύεͷੜσʔλͷαΠζʹର͢Δѹॖ཰Ͱ୯Ґ͸%ɼ
ʮLookupʯͱʮAccessʯ͸ͦΕͧΕ 1 ճ౰ͨΓͷ࣮ߦ࣌ؒͰ୯Ґ͸ϚΠΫϩ
ඵͰ͋ΔɽLookup/Access ͷ࣮ߦ࣌ؒΛ‫ܭ‬ଌ͢ΔͨΊʹɼίʔύε͔ΒϥϯμϜʹநग़ͨ͠ 100 ສ‫ݸ‬ͷจࣈྻɼ‫ͦͼٴ‬ͷจࣈྻʹରԠ͢Δ 100 ສ‫ݸ‬ͷ ID Λ༻͍ͨɽͦΕͧΕɼ10 ճͷࢼߦ͔ΒಘΒΕͨ݁Ռͷฏ‫͋Ͱۉ‬Δɽ

5. 2. 1 C-Trie ͷ݁Ռʢද 3aʣʹର͢ΔධՁ
ߏங࣌ؒʹؔͯ͠͸ɼ͍ͣΕ΋ TAIL ͕ߴ଎Ͱ͋ΓɼPRDT͕௿଎Ͱ͋ͬͨɽ͔͠͠ɼͦͷࠩ͸ߴʑ1.4 ഒͰ͋ΓେࠩͰ͸ͳ͍ɽѹॖ཰ʹؔͯ͠͸ɼRPT2 ͕૯ͯ͡ߴ͘ɼLookup/Accessͷ࣮ߦ࣌ؒʹؔͯ͠͸ɼTAIL ͕૯ͯ͡༏Ε͍ͯͨɽ৽ఏҊͷิॿจࣈྻࣙॻʹؔͯ͠ɼSW ͷΑ͏ʹฏ‫ۉ‬௕͕ൺֱత୹͍৔
߹ʹ͸ RPDT ͕ɼSI ΍ SU ͷΑ͏ʹ௕͍৔߹ʹ͸ FBC4 ͕ɼશମͷόϥϯεͱͯ͠༏Ε͍ͯͨɽ͔͠͠ɼͲͪΒͷੑೳ΋

TAIL ͱ RPT1 ͷؒʹҐஔ͠ɼC-Trie ʹద༻͢Δ্ͰಛผͲ
ͷิॿจࣈྻࣙॻ͕༏Ε͍ͯΔͱ͍ͬͨ݁Ռ͸ಘΒΕͳ͔ͬͨɽ

5. 2. 2 PD-Trie ͷ݁Ռʢද 3bʣʹର͢ΔධՁ
ߏங࣌ؒʹؔͯ͠͸ɼ͍ͣΕ΋ Plain ͕ߴ଎Ͱ͋ͬͨɽิॿ
จࣈྻࣙॻΛ༻͍ͨ৔߹ͷߏங࣌ؒ͸ɼ͍ͣΕ΋͍ۙ஋ΛऔΓɼPlain ͱൺ΂ͯ࠷େͰ 3.4 ഒ௿଎Ͱ͋ͬͨɽҰํɼRe-Pair Λ༻͍࣮ͨ૷͸ɼߏஙίετΛҰఆʹ཈͑ΔΑ͏ͳ࣮૷Λ͍ͯ͠Δ
΋ͷͷɼPlain ͱൺ΂ͯ࠷େͰ 15 ഒ΋௿଎Ͱ͋ͬͨɽ͜ͷ͜ͱ͔ΒɼิॿจࣈྻࣙॻΛ༻͍ͨ৔߹ͷߏஙίετ͸ɼৗʹ௿҆͘ఆ͍ͯ͠Δɽิॿจࣈྻࣙॻʹ͓͍ͯɼѹॖ཰ʹؔͯ͠͸ RPT2ɼBC16
͕༏Εͨ݁ՌͰ͋Δ΋ͷͷɼLookup/Access ͷ࣮ߦ͕࣌ؒඇ
ৗʹ௿଎Ͱ͋Δɽѹॖ཰ͱ࣮ߦ࣌ؒͷόϥϯεͰ༏Ε͍ͯΔ
ͷ͸ RPDT ͱ FBC4ɼFBC8 Ͱ͋ΓɼRe-Pair ͱൺ΂ͯɼSW
ʹ͓͚Δ FBC Λআ͍ͯѹॖ཰ͱ࣮ߦ࣌ؒͰ͍ۙ஋Λ͍ࣔͯ͠Δɽ͜ΕʹՃ͑ͯߏங͕࣌ؒ୹͍͜ͱ͕ɼैདྷͷѹॖʹର͢Δ

RPDT ͱ FBC4ɼFBC8 ͷར఺ͱ͍͑Δɽ· ͨ ɼ஫ ໨ ͢ ΂ ͖ ఺ ͱ ͠ ͯ ɼPlain Α Γ ΋ TAIL ͷ ํ ͕

Lookup/Access ͷ࣮ߦ࣌ؒͰ্ճͬͨͱ͍͏఺͕͋͛ΒΕΔɽ͜ͷཁҼͱͯ͠͸ɼࣙॻූ߸ԽʹΑΓ Elias-Fano ද‫ʹݱ‬ΑΔઅ఺ϥϕϧͷ‫ڥ‬քͷ෮‫͕ݩ‬ඞཁͳ͘ͳͬͨ͜ͱ͕͋͛ΒΕɼࣙॻූ߸ԽʹΑΔѹॖ͕ޮ཰తʹಇ͍ͨ 1 ͭͷྫͱ͍͑Δɽ·ͨɼTAIL ʹΑΔѹॖ཰΋ɼSI ΍ SU Ͱ͸ Re-Pair ͱൺ΂ 2–3%͔͠ҧΘͳ͍ɽ෮‫ݩ‬଎౓Λॏࢹͨ͠ଞͷσʔλѹॖΛ༻͍ͨͱͯ͠΋ɼ୯७ͳจࣈྻࢀরͰ͋Δ TAIL ΑΓߴ଎ʹͳ
Δͱ͸ߟ͑ͮΒ͘ɼLookup/Access ͷ࣮ߦ࣌ؒΛॏࢹ࣮ͨ͠૷
ʹ͓͍ͯɼTAIL ͸༏ΕͨखஈͱͳΔɽද 3: ࣮‫݁ݧ‬Ռ(a) C-TrieSWߏங࣌ؒ ѹॖ཰

SI

SU

Lookup Access ߏங࣌ؒ ѹॖ཰ Lookup Access ߏங࣌ؒ ѹॖ཰ Lookup Access

TAIL

8.5

34.0

1.11

1.13

8.3

11.7

1.47

1.61

1.59

1.68

1.67

1.87

48.1

RCT1

10.1

26.1

RCT2

10.4

24.9

9.1

8.1

9.3

7.2

RPDT

11.8

27.6

1.39

1.42

9.6

9.5

BC4

11.2

30.8

2.05

1.37

9.2

9.6

BC8

11.1

29.2

2.23

1.45

9.2

9.1

5.67

BC16

11.1

28.3

2.59

1.63

9.2

8.8

FBC4

11.1

31.6

1.46

1.32

9.2

9.9

FBC8

11.1

30.9

1.53

1.36

9.3

9.8

FBC16

11.0

30.9

1.65

1.43

9.2

9.9

19.0

2.46

2.65

2.87

3.20

57.0

13.4

4.47

4.51

3.44

3.82

59.5

12.1

5.22

5.22

2.25

2.73

65.2

15.0

3.53

3.70

4.26

2.55

61.4

15.5

5.24

3.59

3.56

61.3

14.6

5.87

3.95

7.45

4.66

61.1

14.1

7.07

4.64

2.07

2.34

61.7

15.9

3.28

3.19

2.37

2.61

61.2

15.5

3.47

3.29

2.86

2.84

61.4

15.5

3.83

3.50

(b) PD-TrieSWߏங࣌ؒ ѹॖ཰

SI

SU

Lookup Access ߏங࣌ؒ ѹॖ཰ Lookup Access ߏங࣌ؒ ѹॖ཰ Lookup Access

Plain

2.1

49.6

1.25

1.42

2.5

24.5

1.39

1.78

12.8

27.1

1.89

Re-Pair

29.0

31.6

1.31

1.48

20.3

11.8

1.63

2.00

185.6

17.5

2.06

2.26
2.42

TAIL

4.7

41.7

1.13

1.26

4.0

13.5

1.23

1.56

24.1

20.7

1.67

1.96

RCT1

6.7

31.3

2.51

2.57

4.8

9.1

2.91

3.16

32.3

14.8

4.14

4.28

RCT2

7.2

29.3

3.66

3.63

5.0

8.2

4.55

4.75

35.5

13.4

6.55

6.57

RPDT

7.2

32.4

1.51

1.60

4.8

10.7

1.68

1.92

33.8

16.4

2.48

2.67

BC4

6.5

36.0

3.38

3.66

4.5

10.9

5.24

5.75

31.0

16.9

5.71

6.24

BC8

6.5

33.8

3.71

3.96

4.5

10.3

6.09

6.64

31.1

15.9

6.58

7.12

BC16

6.5

32.7

4.48

4.77

4.5

10.0

7.73

8.27

30.9

15.4

8.28

8.79

FBC4

6.5

37.0

1.61

1.74

4.5

11.3

1.78

2.08

31.1

17.3

2.42

2.69

FBC8

6.5

35.9

1.73

1.85

4.5

11.2

2.00

2.30

31.2

16.9

2.64

2.92

FBC16

6.5

35.9

1.97

2.12

4.5

11.3

2.40

2.73

31.2

16.9

3.03

3.33

(c) Front-CodingSWߏங࣌ؒ ѹॖ཰

SI

SU

Lookup Access ߏங࣌ؒ ѹॖ཰ Lookup Access ߏங࣌ؒ ѹॖ཰ Lookup Access

Plain

0.8

59.6

1.11

0.37

0.8

34.9

1.31

0.33

3.8

37.3

1.60

Re-Pair

470.9

36.5

2.09

1.31

1363.8

18.2

2.67

1.66

5861.6

22.3

3.29

0.37
1.91

TAIL

3.7

45.3

1.39

0.69

2.7

25.0

1.72

0.78

17.7

31.4

2.26

0.88

RCT1

5.2

37.4

2.42

1.50

3.6

21.1

2.30

1.22

26.7

25.7

3.84

2.13

RCT2

5.6

36.0

2.63

1.69

3.8

20.1

2.76

1.62

29.2

24.4

4.66

2.85

RPDT

6.2

38.7

1.95

1.10

3.9

22.3

2.13

1.08

30.6

27.1

3.31

1.73

BC4

5.7

41.9

1.82

1.03

3.6

22.5

2.27

1.22

27.3

27.7

3.00

1.54

BC8

5.6

40.2

2.01

1.19

3.6

22.0

2.60

1.54

27.2

26.8

3.40

1.87

BC16

5.6

39.4

2.36

1.56

3.6

21.7

3.37

2.30

27.3

26.4

4.31

2.72

FBC4

5.7

42.7

1.73

0.95

3.6

22.9

1.98

0.98

27.4

28.1

2.64

1.22

FBC8

5.7

42.0

1.78

1.01

3.6

22.7

2.04

1.04

27.4

27.7

2.72

1.30

FBC16

5.6

42.0

1.90

1.14

3.6

22.9

2.20

1.21

27.3

27.7

2.92

1.49

5. 2. 3 Front-Coding ͷ݁Ռʢද 3cʣʹର͢ΔධՁ

Θ͔ͬͨɽFront-Coding ͷ Re-Pair Ͱ͸ɼΦϦδφϧʹ͍ۙߏங࣌ؒɼLookup/Access ͷ࣮ߦ଎౓ʹؔͯ͠ɼPlain ͕૯࣮૷Λ͍ͯ͠Δͱ͍͏͜ͱʹ‫ى‬Ҽ͠ɼ͜Ε΄Ͳʹ΋͕ࠩ޿͕ͬ

ͯ͡࠷΋༏Ε͍ͯΔ͕ɼѹॖ཰ʹؔͯ͠͸େ͖͘ྼΔ݁Ռͱͳͬ

ͨɽҰํͰɼѹॖ཰ʹ͍ͭͯ͸ Re-Pair ͕༏Ε͓ͯΓɼSI ͱͨɽิॿจࣈྻࣙॻΛ༻͍࣮ͨ૷ͷߏங࣌ؒʹؔͯ͠ɼPlain

SU Ͱ͸࠷΋ίϯύΫτʹࣙॻΛߏங͍ͯ͠Δɽ͔͠͠ɼѹॖʹ͸‫ٴ‬͹ͳ͍΋ͷͷɼRe-Pair ͱൺ΂ɼSW Ͱ࠷େ 127 ഒɼSI཰ʹ൓ͯ͠ Lookup/Access ͷ࣮ߦ࣌ؒ͸ൺֱత஗͘ɼͦͷࠩ

Ͱ࠷େ 505 ഒɼSU Ͱ࠷େ 331 ഒͱѹ౗తʹߴ଎Ͱ͋Δ͜ͱ͕͸ TAIL ͱൺ΂ͯ 1.5–2.2 ഒɼFBC4 ͱൺ΂ͯ 1.2–1.7 ഒͱ௿଎Ͱ͋ͬͨɽ࠷ ‫ ʹ ޙ‬ɼRPDT ͱ FBC4 Λ Re-Pair ʹ ର ͠ ൺ ֱ ͢ Δ ͱ ɼ

RPDT ͱ FBC4 ͸ѹॖ཰Ͱ 2–6%ྼΔ΋ͷͷɼLookup/Accessͷ࣮ߦ࣌ؒ͸ 1.1–1.7 ഒߴ଎Ͱ͋Γɼߏங࣌ؒ͸ 76–379 ഒͱѹ౗తʹߴ଎Ͱ͋Δɽ͜ΕΑΓɼิॿจࣈྻࣙॻ͸ Re-Pair ΑΓ΋‫࣮ݱ‬తͳѹॖखஈͱ͍͑Δɽ

6. ͓ Θ Γ ʹຊߘͰ͸ɼจࣈྻࣙॻͷѹॖʹࣙॻූ߸ԽΛ༻͍Δํࡦʹ‫ج‬͖ͮɼ‫ط‬ଘͷࣙॻߏ଄ʹࣙॻූ߸ԽΛద༻͢Δํ๏ɼ‫ࣙͼٴ‬ॻѹॖͷͨΊͷࣙॻߏ଄ΛఏҊͨ͠ɽຊ࣮‫Ͱݧ‬͸ɼPD-Trieɼ

Front-Coding ͱ΋ʹɼͦΕͧΕͷఏҊऀ͕ద༻ͨ͠ Re-Pairͷ࣮૷ΛϕʔεϥΠϯͱͯ͠༻͍͕ͨɼߏஙίετɼѹॖ཰ɼ෮‫ݩ‬଎౓ͳͲɼͲ͜ʹॏ఺Λஔ͔͘ʹΑͬͯɼRe-Pair ͷ࣮૷΍ద༻͢Δσʔλѹॖ๏ͳͲʹ͸બ୒ͷ༨஍͕͋Δɽ͔͠͠ɼ

RPDT ΍ FBC ʹΑΓѹॖͨࣙ͠ॻ͸ Re-Pair ѹॖʹΑΔࣙ
ॻͱൺ΂ɼѹॖ཰ɼLookup/Access ͷ࣮ߦ࣌ؒͷτϨʔυΦϑʹ͓͍ͯಉ౳ͷੑೳΛࣔͭͭ͠ɼߏஙίετʹؔͯ͠େ͖͘
্ճͬͨͱ͍͏݁Ռ͔Βɼࣙॻූ߸ԽʹΑΔѹॖ͸༗ޮͳखஈ
ͷ 1 ͭͱͳΓಘΔɽͨͩ͠ɼຊ࣮‫Ͱݧ‬͸ߏஙʹ͓͚Δ࡞‫ྖۀ‬Ҭʹ͍ͭͯͷධՁΛ༩͑ΒΕ͍ͯͳ͍ͨΊɼͦΕ͸ࠓ‫ޙ‬ͷ՝୊ͱͳΔɽ
·ͨຊߘͰ͸ɼจࣈྻࣙॻʹର͢Δࣙॻූ߸Խͷద༻Λߟ࡯͕ͨ͠ɼ෦෼తʹଟ਺ͷจࣈྻ͕‫ݱ‬ΕΔσʔλߏ଄Ͱ͋Ε͹ɼಉ༷ͷѹॖ͕ద༻Ͱ͖ΔɽͱΓΘ͚ɼPD-Trie ΁ͷద༻Ͱ

Elias-Fano ද‫͕ݱ‬औΓআ͚ͨΑ͏ʹɼจࣈྻΛ੔਺஋ʹஔ͖‫׵‬
͑Δ͜ͱʹΑΓར఺͕‫͍ͤͩݟ‬Δσʔλߏ଄Ͱ͋Ε͹ɼࣙॻූ߸ԽʹΑΔѹॖ͸ޮՌతͰ͋Δɽࠓ‫ޙ‬ͷ༧ఆͱͯ͠͸ɼͦ͏ͨ͠σʔλߏ଄ͷௐࠪͱద༻࣮‫͕͛͋ݧ‬ΒΕΔɽจ‫ݙ‬[1] Miguel A Martı́nez-Prieto, Nieves Brisaboa, RodrigoCánovas, Francisco Claude, and Gonzalo Navarro. Practical compressed string dictionaries. Information Systems,
56:73–108, 2016.
[2] Roberto Grossi and Giuseppe Ottaviano. Fast compressed
tries through path decompositions. ACM Journal of Experimental Algorithmics, 19(1):Article 1.8, 2014.
[3] Julian Arz and Johannes Fischer. LZ-compressed string dictionaries. In DCC, pages 322–331, 2014.
[4] Shunsuke Kanda, Kazuhiro Morita, and Masao Fuketa.
Compressed double-array tries for string dictionaries supporting fast lookup. Knowledge and Information Systems,
Online First, 2016.
[5] ໼ా ৾. Prefix/patricia trie ͷೖΕࢠʹΑΔࣙॻѹॖ. In ‫ޠݴ‬ॲཧֶձ, 2011.
[6] Ian H Witten, Alistair Moﬀat, and Timothy C Bell. Managing gigabytes: compressing and indexing documents andimages. Morgan Kaufmann, San Francisco, CA, USA, 1999.
[7] Donald E Knuth. The art of computer programming, 3:sorting and searching. Addison Wesley, Redwood City, CA,
USA, 2nd edition, 1998.
[8] Paolo Ferragina, Roberto Grossi, Ankur Gupta, Rahul
Shah, and Jeﬀrey Scott Vitter. On searching compressed
string collections cache-obliviously. In PODS, pages 181–
190. ACM, 2008.

[9] N. Jesper Larsson and Alistair Moﬀat. Oﬀ-line dictionarybased compression. Proc. the IEEE, 88(11):1722–1732,
2000.
[10] Guy Jacobson. Space-eﬃcient static trees and graphs. In
FOCS, pages 549–554. IEEE, 1989.
[11] David Benoit, Erik D Demaine, J Ian Munro, Rajeev Raman, Venkatesh Raman, and S Srinivasa Rao. Representing
trees of higher degree. Algorithmica, 43(4):275–292, 2005.
[12] J Ian Munro and Venkatesh Raman. Succinct representation of balanced parentheses and static trees. SIAM Journal
on Computing, 31(3):762–776, 2001.
[13] Peter Elias. Eﬃcient storage and retrieval by content andaddress of static files. Journal of the ACM, 21(2):246–260,
1974.
[14] Robert Mario Fano. On the number of bits required to implement an associative memory. Memorandum 61, Computer
Structures Group, MIT, Cambridge, MA, 1971.
[15] Roberto Grossi and Giuseppe Ottaviano. Design of practical succinct data structures for large data collections. In
SEA, pages 5–17, 2013.
[16] Hugh E Williams and Justin Zobel. Compressing integers
for fast file access. Computer Journal, 42(3):193–201, 1999.
[17] Francisco Claude and Gonzalo Navarro. Fast and compact
web graph representations. ACM Transactions on the Web,
4(4):16, 2010.
[18] Ingo Müller, Cornelius Ratsch, and Franz Faerber. Adaptive
string dictionary compression in in-memory column-store
database systems. In EDBT, pages 283–294, 2014.