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
710
Fast Succinct Trie
第七回StringBeginnersでの発表資料です。
Shunsuke Kanda
August 06, 2019
Tweet
Share
More Decks by Shunsuke Kanda
See All by Shunsuke Kanda
Leveraging LLMs for Unsupervised Dense Retriever Ranking (SIGIR 2024)
kampersanda
2
370
Lucene/Elasticsearch の Character Filter でユニコード正規化するとトークンのオフセットがズレるバグへの Workaround - Search Engineering Tech Talk 2024 Spring
kampersanda
0
1.4k
Binary and Scalar Embedding Quantization for Significantly Faster & Cheaper Retrieval
kampersanda
2
390
トライとダブル配列の基礎
kampersanda
0
1.2k
Binary search with modern processors
kampersanda
30
13k
AIP Open Seminar #6
kampersanda
0
230
ICDM2020
kampersanda
0
210
SIGSPATIAL20
kampersanda
0
190
EliasFano
kampersanda
1
230
Other Decks in Research
See All in Research
Adaptive Experimental Design for Efficient Average Treatment Effect Estimation and Treatment Choice
masakat0
0
130
【緊急警告】日本の未来設計図 ~沈没か、再生か。国民と断行するラストチャンス~
yuutakasan
0
130
MGDSS:慣性式モーションキャプチャを用いたジェスチャによるドローンの操作 / ec75-yamauchi
yumulab
0
240
作業記憶の発達的特性が言語獲得の臨界期を形成する(NLP2025)
chemical_tree
2
610
データxデジタルマップで拓く ミラノ発・地域共創最前線
mapconcierge4agu
0
170
実行環境に中立なWebAssemblyライブマイグレーション機構/techtalk-2025spring
chikuwait
0
220
NLP Colloquium
junokim
1
150
さくらインターネット研究所 アップデート2025年
matsumoto_r
PRO
0
650
Ad-DS Paper Circle #1
ykaneko1992
0
5.5k
Large Language Model Agent: A Survey on Methodology, Applications and Challenges
shunk031
12
8.2k
数理最適化と機械学習の融合
mickey_kubo
15
8.8k
線形判別分析のPU学習による朝日歌壇短歌の分析
masakat0
0
130
Featured
See All Featured
How to Create Impact in a Changing Tech Landscape [PerfNow 2023]
tammyeverts
53
2.8k
For a Future-Friendly Web
brad_frost
179
9.8k
CoffeeScript is Beautiful & I Never Want to Write Plain JavaScript Again
sstephenson
161
15k
Rails Girls Zürich Keynote
gr2m
94
14k
StorybookのUI Testing Handbookを読んだ
zakiyama
30
5.8k
The Language of Interfaces
destraynor
158
25k
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
194
16k
Balancing Empowerment & Direction
lara
1
380
Measuring & Analyzing Core Web Vitals
bluesmoon
7
490
Building a Modern Day E-commerce SEO Strategy
aleyda
42
7.3k
Rebuilding a faster, lazier Slack
samanthasiow
82
9.1k
Improving Core Web Vitals using Speculation Rules API
sergeychernyshev
17
940
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