Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Fast Succinct Trie
Search
Shunsuke Kanda
August 06, 2019
Research
1
560
Fast Succinct Trie
第七回StringBeginnersでの発表資料です。
Shunsuke Kanda
August 06, 2019
Tweet
Share
More Decks by Shunsuke Kanda
See All by Shunsuke Kanda
Binary and Scalar Embedding Quantization for Significantly Faster & Cheaper Retrieval
kampersanda
0
8
トライとダブル配列の基礎
kampersanda
0
630
Binary search with modern processors
kampersanda
30
13k
AIP Open Seminar #6
kampersanda
0
140
ICDM2020
kampersanda
0
120
SIGSPATIAL20
kampersanda
0
90
EliasFano
kampersanda
1
170
StringBeginners#1
kampersanda
2
150
Ph.D. Thesis
kampersanda
0
360
Other Decks in Research
See All in Research
生成AIを用いたText to SQLの最前線
masatoto
1
2.8k
LiDARセキュリティ最前線
kentaroy47
0
290
ICLR2024 LLMエージェントの研究動向
masatoto
9
4.1k
機械学習と最適化の融合動的ロットサイズ決定問題を例として
mickey_kubo
2
300
機械学習と数理最適化の融合-文脈付き確率的最短路を例として-
mickey_kubo
2
530
Generative Spoken Dialogue Language Modeling [対話論文読み会@電通大]
yuta0306
1
150
インタビューだけじゃない!ユーザーに共感しユーザーの目👀を手に入れるためのインプット
moco1013
0
310
Accurate Method and Variable Tracking in Commit History
tsantalis
0
300
Embodied AIについて / About Embodied AI
nttcom
1
690
メタ動画データセットによる動作認識の現状と可能性
yuyay
0
250
リサーチに組織を巻き込むための「準備8割」の話
terasho
0
480
クロスモーダル表現学習の研究動向: 音声関連を中心として
ryomasumura
3
640
Featured
See All Featured
Docker and Python
trallard
35
2.7k
What the flash - Photography Introduction
edds
64
11k
Building a Scalable Design System with Sketch
lauravandoore
457
32k
Exploring the Power of Turbo Streams & Action Cable | RailsConf2023
kevinliebholz
8
3.5k
How STYLIGHT went responsive
nonsquared
92
4.8k
It's Worth the Effort
3n
180
27k
Product Roadmaps are Hard
iamctodd
45
9.8k
The Cult of Friendly URLs
andyhume
74
5.7k
RailsConf 2023
tenderlove
9
580
Automating Front-end Workflow
addyosmani
1357
200k
No one is an island. Learnings from fostering a developers community.
thoeni
16
2.1k
Happy Clients
brianwarren
92
6.4k
Transcript
'BTU4VDDJODU5SJF @kampersanda 7th StringBeginners հจɿ ;IBOH -JN -FJT "OEFSTFO ,BNJOTLZ
,FFUPOBOE1BWMP 4V3'1SBDUJDBM3BOHF2VFSZ'JMUFSJOHXJUI'BTU4VDDJODU5SJF *O4*(.0% QQ
'BTU4VDDJODU5SJF '45 w ͷ4*(.0%ͰఏҊ͞Εͨ؆ܿ5SJFදݱ ;IBOHFUBM4V3'1SBDUJDBMSBOHFRVFSZpMUFSJOHXJUI GBTUTVDDJODUUSJFT4*(.0% 4VDDJODU3BOHF'JMUFS
4V3' ͷͨΊʹఏҊ͞Εͨ Ұൠతͳ༻్ʹ͑Δ w ࠓճͷൃද4V3'Ͱͳ͘'45ʹযΛͯͨͷͰ͢ w ͪͳΈʹ ච಄ஶऀ͞ΜʹΑΔΘ͔Γ͍͢εϥΠυ͕͏͢Ͱʹ͋Γ·͢ ‣ IUUQXXXDTDNVFEVdIVBODIFTMJEFT'45QEG ࠓճͷ୯७ʹͦΕΛͳͧͬͨͷͰͳ͍Ͱ͢ 2
5SJFࣙॻ w 5SJFͱҰݴͰݴͬͯɺٻΊΒΕΔૢ࡞͍Ζ͍Ζ w ࠓճ؆୯ʹҎԼͷΑ͏ͳૢ࡞͕Ͱ͖ΕΑ͠ͱ͠·͢ .FNCFS 4 ɿจࣈྻ4͕Ωʔͱؚͯ͠·Ε͍ͯΔ͔ʁ
1SFpY 4 ɿจࣈྻ4ͷ಄ࣙͱ࠷Ұக͢ΔΩʔʁ 3 .FNCFS Θͨ͠ :FT .FNCFS Θͨ͘͠ /P 1SFpY Θͨ͘͠ Θͨ ͨ Θ ʹ ͠ Έ ͨ Θ ͠
ͦͦ؆ܿ5SJFͬͯԿʁ 'BTU4VDDJODU5SJF '45 ͱʁ 5SJFࣙॻͱͯ͠ͷ'45ͷੑೳʁ
ͦͦ؆ܿ5SJFͬͯԿʁ 'BTU4VDDJODU5SJF '45 ͱʁ 5SJFࣙॻͱͯ͠ͷ'45ͷੑೳʁ
؆ܿ5SJFͱʁ w ใཧతԼݶʹ͍ۙϝϞϦྔͰ5SJFΛදݱ͢Δσʔλߏ OMHМ 0 O Ϗοτ ‣ OઅɺМΞϧϑΝϕοταΠζ
w ʮॱংͷ؆ܿදݱʯ ʮϥϕϧͷྻʯͰΑ͘දݱ͞ΕΔ w ̏ͭͷදతͳॱংͷ؆ܿσʔλߏ #1 #BMBODFE1BSFOUIFTFT %'6%4 %FQUI'JSTU6OBSZ%FHSFF4FRVFODF -06%4 -FWFM0SEFSFE6OBSZ%FHSFF4FRVFODF w ͪͳΈʹɺ 9#8N#POTBJͳͲ؆ܿ5SJFͰ͕͢ࠓճѻΘͳ͍Ͱ͢ 6 O P O CJUT OMPHМCJUT
#1 #BMBODFE1BSFOUIFTFT w ֤અΛ։ׅހ(ͱดׅހ)ͷϖΞͰදݱ ਂ͞༏ઌॱͰΛࠪ ߦ͖ͷ๚Ͱ(Λஔ͖ɺؼΓͷ๚Ͱ)Λஔ͘ 7
'JSTU$IJME QPT QPT /FYU4JCMJOH QPT 'JOE$MPTF QPT ( ( ( ) ( ( ) ( ) ) ) ( ( ( ) ) ) ) 'JOE$MPTFɿରԠ͢ΔดׅހͷҐஔ
%'6%4 %FQUI'JSTU6OBSZ%FHSFF4FRVFODF w #1ΑΓଟػೳͳׅހྻදݱ ਂ͞༏ઌॱͰΛࠪ ֤અʹ͍ͭͯɺͦͷࢠͱಉ͡ͷ(ͱ̍ݸͷ)Λஔ͘ ࠷ޙʹઌ಄ʹ(Λஔ͘
8 ( ( ( ) ( ( ) ) ( ( ) ) ) ( ) ( ) ) $IJME QPT J 'JOE$MPTF 4FMFDU) 3BOL) QPT J 3BOLb QPT ɿQPT·Ͱͷbͷ 4FMFDUb L ɿL൪ͷb͕ݱΕΔҐஔ 'JOE$MPTF
-06%4 -FWFM0SEFSFE6OBSZ%FHSFF4FRVFODF w ͜ͷੈͰͬͱγϯϓϧͳදݱʢྑ͍ҙຯͰʣ ෯༏ઌॱʹΛࠪ ֤અʹ͍ͭͯɺͦͷࢠͱಉ͡ͷ1ͱ̍ݸͷ0Λஔ͘ ࠷ޙʹઌ಄ʹ10Λஔ͘
9 1 0 1 1 0 1 1 0 1 0 0 1 1 0 1 0 0 0 0 'JSTU$IJME QPT 4FMFDU0 3BOL1 1PT /FYU4JCMJOH QPT QPT 3BOLb QPT ɿQPT·Ͱͷbͷ 4FMFDUb L ɿL൪ͷb͕ݱΕΔҐஔ 'JSTU$IJME
؆ܿ5SJFͷϨϏϡʔ 10 ػೳੑ ݕࡧ ࣮ #1 ̋ ˚ %'6%4
˕ ̋ -06%4 ˚ ˕ қ w Ұൠతʹɺࣙॻͱͯ͠ͷ5SJF಄ࣙݕࡧ͕Ͱ͖Εे w #1ͱ%'6%4Ϧον͗͢ΔͷͰ-06%4͕࠾༻͞ΕΔέʔε͕ଟ͍ 59ɺ69ɺ."3*4"ɺ'45ɺͳͲ w ͦͷลΓͷൺֱ࣮ݧ "SSPZVFMPFUBM4VDDJODUUSFFTJOQSBDUJDF"-&/&9 ాΒॱংͷ؆ܿදݱΛ༻͍ͨτϥΠࣙॻͷධՁॲશࠃ ࠓͱͳͬͯ ͦ͜·Ͱ͡Όͳ͍
ͦͦ؆ܿ5SJFͬͯԿʁ 'BTU4VDDJODU5SJF '45 ͱʁ 5SJFࣙॻͱͯ͠ͷ'45ͷੑೳʁ
ઃܭͷϞνϕʔγϣϯ w ࠜͷۙͷઅͱ༿ͷۙͷઅͰੑׂ࣭͕ҧ͏ 12 w ͪͳΈʹɺͦͷΑ͏ͳϞνϕʔγϣϯ౷తʹ͋Γ·͢ "35ɿઅͷ࣍ʹΑΓదͳσʔλߏΛબ #VSTU5SJF)"5ɿࠜۙͷઅΛ୯७ͳྻͰදݱ
."3*4"ɿࠜͷۙͷ3BOL4FMFDUͷԋࢉ݁ՌΛΩϟογϡ ૄ සൟʹΞΫηε͞ΕΔ େଟͷઅ͕ଐ͢Δ ͕େࣄʂ ϝϞϦޮ͕େࣄʂ ͨ Θ ʹ ͠ Έ ͨ Θ ͠ ີ
-06%4%4ɿೋछྨͷ-06%4Ͱදݱ 13 ਤจΑΓҾ༻ w ࠜۙߴͳ-06%4%FOTF w ༿ۙϝϞϦޮͷྑ͍-06%44QBSTF
-06%4%FOTF 14 - )$ ͨ Θ ʹ ͠ Έ ͨ
Θ ͠ - )$ ͨ Θ Θ ͨ ʹ - )$ ͠ ͠ Έ ˞ଟগɺ؆ུԽͯ͠·͢ w -ɿͦͷࢬϥϕϧΛ࣋ͭࢠ͕ଘࡏ͢Δ͔ʁ w )$ɿͦͷࢠ෦અ͔ʁ МޒेԻ w ֤෦અΛ͞Мͷ ϏοτϚοϓͰදݱ
-06%4%FOTF 15 - )$ ͨ Θ ʹ ͠ Έ ͨ
Θ ͠ - )$ ͨ Θ Θ ͨ ʹ - )$ ͠ ͠ Έ ॳظঢ়ଶɿQPT ʮΘͨ͠ʯͰݕࡧ ߋ৽ɿQPTQPT จࣈ ֬ೝɿ-<QPT>ͳΒࢠ͕ଘࡏ͠ɺ)$<QPT>ͳΒͦͷࢠ෦અ ભҠɿ$IJME1PT QPT Мº3BOL )$ QPT QPT М ˞ଟগɺ؆ུԽͯ͠·͢
-06%4%FOTF 16 ͨ Θ ʹ ͠ Έ ͨ Θ ͠
ͨ Θ Θ ͨ ʹ ͠ ͠ Έ QPT $IJME1PT ʮΘͨ͠ʯͰݕࡧ М ˞ଟগɺ؆ུԽͯ͠·͢ - )$ - )$ - )$ QPT ߋ৽ɿQPTQPT จࣈ ֬ೝɿ-<QPT>ͳΒࢠ͕ଘࡏ͠ɺ)$<QPT>ͳΒͦͷࢠ෦અ ભҠɿ$IJME1PT QPT Мº3BOL )$ QPT 3BOL )$ QPT
-06%4%FOTF 17 ͨ Θ ʹ ͠ Έ ͨ Θ ͠
ͨ Θ Θ ͨ ʹ ͠ ͠ Έ QPT $IJME1PT ʮΘͨ͠ʯͰݕࡧ М ˞ଟগɺ؆ུԽͯ͠·͢ - )$ - )$ - )$ QPT ߋ৽ɿQPTQPT จࣈ ֬ೝɿ-<QPT>ͳΒࢠ͕ଘࡏ͠ɺ)$<QPT>ͳΒͦͷࢠ෦અ ભҠɿ$IJME1PT QPT Мº3BOL )$ QPT 3BOL )$ QPT
-06%4%FOTF 18 ͨ Θ ʹ ͠ Έ ͨ Θ ͠
ͨ Θ Θ ͨ ʹ ͠ ͠ Έ QPT )$<QPT>ͳͷͰ༿ ʮΘͨ͠ʯͰݕࡧ М ˞ଟগɺ؆ུԽͯ͠·͢ - )$ - )$ - )$ QPT ߋ৽ɿQPTQPT จࣈ ֬ೝɿ-<QPT>ͳΒࢠ͕ଘࡏ͠ɺ)$<QPT>ͳΒͦͷࢠ෦અ ભҠɿ$IJME1PT QPT Мº3BOL )$ QPT
-06%44QBSTF 19 ͨ Θ
ʹ ͠ Έ ͨ Θ ͠ - ͨ Θ Θ ͨ ʹ ͠ ͠ Έ )$ 4 ˞ଟগɺ؆ུԽͯ͠·͢ w ݪཧతʹී௨ͷ-06%4ͱҰॹ w-ɿϥϕϧͷྻ w)$ɿͦͷઅ෦અ͔ʁ w4ɿͦͷઅஉ͔ʁʢݪཧతʹී௨ͷ-06%4ʣ
-06%44QBSTF 20 ʮΘͨ͠ʯͰݕࡧ
- ͨ Θ Θ ͨ ʹ ͠ ͠ Έ )$ 4 ୳ࡧɿQPT -<QPT>จࣈ ͳQPT ֬ೝɿ)$<QPT>ͳΒͦͷࢠ෦અ ભҠɿ$IJME1PT QPT 4FMFDU 4 3BOL )$ QPT ˞ଟগɺ؆ུԽͯ͠·͢ ॳظঢ়ଶɿQPT QPT ͨ Θ ʹ ͠ Έ ͨ Θ ͠
-06%44QBSTF 21 ʮΘͨ͠ʯͰݕࡧ
- ͨ Θ Θ ͨ ʹ ͠ ͠ Έ )$ 4 ˞ଟগɺ؆ུԽͯ͠·͢ QPT $IJME1PT QPT ୳ࡧɿQPT -<QPT>จࣈ ͳQPT ֬ೝɿ)$<QPT>ͳΒͦͷࢠ෦અ ભҠɿ$IJME1PT QPT 4FMFDU 4 3BOL )$ QPT ͨ Θ ʹ ͠ Έ ͨ Θ ͠ 3BOL )$ QPT 4FMFDU 4
ͨ Θ ʹ ͠
Έ ͨ Θ ͠ -06%44QBSTF 22 ʮΘͨ͠ʯͰݕࡧ - ͨ Θ Θ ͨ ʹ ͠ ͠ Έ )$ 4 ˞ଟগɺ؆ུԽͯ͠·͢ QPT $IJME1PT ୳ࡧɿQPT -<QPT>จࣈ ͳQPT ֬ೝɿ)$<QPT>ͳΒͦͷࢠ෦અ ભҠɿ$IJME1PT QPT 4FMFDU 4 3BOL )$ QPT 3BOL )$ QPT 4FMFDU 4
-06%44QBSTF 23 ʮΘͨ͠ʯͰݕࡧ
- ͨ Θ Θ ͨ ʹ ͠ ͠ Έ )$ 4 ˞ଟগɺ؆ུԽͯ͠·͢ QPT )$<QPT>ͳͷͰ༿ ୳ࡧɿQPT -<QPT>จࣈ ͳQPT ֬ೝɿ)$<QPT>ͳΒͦͷࢠ෦અ ભҠɿ$IJME1PT QPT 4FMFDU 4 3BOL )$ QPT ͨ Θ ʹ ͠ Έ ͨ Θ ͠
'45ͷͦͷଞͷ w -06%4%FOTF4QBSTFͦΕͧΕʹదͳ3BOLࣙॻͷઃܭ w 4*.%ʹΑΔϥϕϧ୳ࡧͷߴԽ w ϓϦϑΣον໋ྩͷ׆༻ 24 ਤจΑΓҾ༻
ͦͦ؆ܿ5SJFͬͯԿʁ 'BTU4VDDJODU5SJF '45 ͱʁ 5SJFࣙॻͱͯ͠ͷ'45ͷੑೳʁ
'45ͷԠ༻ɿ3BOHF2VFSZ'JMUFSJOH w '453BOHF2VFSZ'JMUFSJOHͷҝͷσʔλߏͱͯ͠ఏҊ͞Εͨ 26 * $ % . & .
- ɿ*$"-1͔Β*$%.ͷؒʹؚ·ΕΔσʔλ͋Δʁ ղɿ:&4ʢ*$%&ͱ*$%.ʣ ɿ*$"-1͔Β*$%.ͷؒʹؚ·ΕΔσʔλʁ ղɿͭʢ*$%&ͱ*$%.ʣ w 4V3' 4VDDJODU3BOHF'JMUFS Ͱ'45ͷར༻ʹՃ͑ɺϢχʔΫͳ ඌࣙΛΓޡݕग़Λڐ͢͜ͱͰɺ#MPPN'JMUFSʹඖఢ͢ΔϝϞϦ༻ྔ Ͱ3BOHF2VFSZ'JMUFSJOHΛ࣮ݱ͢Δ
'45ͷੑೳʢจΑΓҾ༻ʣ w طଘͷ؆ܿ5SJFࣙॻͱൺͯ 27 ϏοτΛόΠτจࣈྻͱͯ͠ ϗετ໊Λͻͬ͘Γฦͯ͠ FH DPNHPPMHF!LBOEB UYUSJFγϯϓϧͳ-06%4 1%5ܦ࿏ղ
%'6%4
'45ͷੑೳʢจΑΓҾ༻ʣ w CJUJOUͰ-06%4%FOTFͷߩݙ͕େ͖͍ Ұ༷Ͱੜ͞Εͨσʔλ ͳͷͰ֤અͷࢠͷ͕ͱͯେ͖͍ 28 CBTFMJOF-06%44QBSTFͷΈ w
5SJFࣙॻͱͯͪ͠ΐͬͱಛघͳσʔληοτʁ w ࣗવݴޠͳͲσʔληοτͰͷੑೳͲ͏ͳͷʁ
5SJFࣙॻɺ࣮͠·ͨ͠ 29 w IUUQTHJUIVCDPNLBNQFSTBOEBGBTU@TVDDJODU@USJF
.FNPSZ6TBHF .J# '45 %"354$ 9$%"5
59 ."3*4" 1%5 4FBSDI5JNF NJDSPTFDRVFSZ '45 %"354$ 9$%"5 59 ."3*4" 1%5 .FNPSZ6TBHF .J# '45 %"354$ 9$%"5 59 ."3*4" 1%5 4FBSDI5JNF NJDSPTFDRVFSZ '45 %"354$ 9$%"5 59 ."3*4" 1%5 30 ࣮ݧʢຊޠʣ ϝϞϦ ݕࡧ *1"ࣙॻ .TUSJOHT BWFMFOHUI 8JLJλΠτϧ .TUSJOHT BWFMFOHUI
31 ࣮ݧʢ"TLJUJT`TEBUBTFUʣ .FNPSZ6TBHF .J# '45
%"354$ 9$%"5 59 ."3*4" 1%5 4FBSDI5JNF NJDSPTFDRVFSZ '45 %"354$ 9$%"5 59 ."3*4" 1%5 ϝϞϦ ݕࡧ %JTUJODU .TUSJOHT BWFMFOHUI 6SM .TUSJOHT BWFMFOHUI .FNPSZ6TBHF .J# '45 %"354$ 9$%"5 59 ."3*4" 1%5 4FBSDI5JNF NJDSPTFDRVFSZ '45 %"354$ 9$%"5 59 ."3*4" 1%5
·ͱΊ w '45γϯϓϧͳ-06%4ͳվྑ w σʔλ͔ΒΔΑ͏ͳઅͷࢠͷ͕ͱͯଟ͍5SJFʹ ରͯ͠ɺ-06%4%FOTFͷߩݙ͕ͱͯେ͖͍ 3BOHFRVFSZpMUFSJOHͷͨΊͷσʔλߏͱͯ͠Α͍ w ҰํͰɺࣗવݴޠσʔλͳͲͰطଘͷ5SJFࣙॻͷํ͕ޮ͕
ྑͦ͞͏ ͔͠͠ͳ͕Βɺ-06%4%FOTFͱଞͷ5SJFࣙॻʢྫ͑ 1%5ͱ͔ʣΛΈ߹ΘͤΔͳͲͷํࡦߟ͑ΒΕͦ͏ 32