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
720
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
380
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
400
トライとダブル配列の基礎
kampersanda
1
1.2k
Binary search with modern processors
kampersanda
33
14k
AIP Open Seminar #6
kampersanda
0
230
ICDM2020
kampersanda
0
210
SIGSPATIAL20
kampersanda
0
200
EliasFano
kampersanda
1
240
Other Decks in Research
See All in Research
定性データ、どう活かす? 〜定性データのための分析基盤、はじめました〜 / How to utilize qualitative data? ~We have launched an analysis platform for qualitative data~
kaminashi
7
1.1k
Large Language Model Agent: A Survey on Methodology, Applications and Challenges
shunk031
13
9.1k
NLP2025参加報告会 LT資料
hargon24
1
330
A scalable, annual aboveground biomass product for monitoring carbon impacts of ecosystem restoration projects
satai
3
110
集合間Bregmanダイバージェンスと置換不変NNによるその学習
wasyro
0
110
EOGS: Gaussian Splatting for Efficient Satellite Image Photogrammetry
satai
4
330
問いを起点に、社会と共鳴する知を育む場へ
matsumoto_r
PRO
0
460
引力・斥力を制御可能なランダム部分集合の確率分布
wasyro
0
200
研究テーマのデザインと研究遂行の方法論
hisashiishihara
5
1.5k
SSII2025 [TS1] 光学・物理原理に基づく深層画像生成
ssii
PRO
4
3.9k
利用シーンを意識した推薦システム〜SpotifyとAmazonの事例から〜
kuri8ive
1
220
データサイエンティストの就労意識~2015→2024 一般(個人)会員アンケートより
datascientistsociety
PRO
0
730
Featured
See All Featured
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
194
16k
What’s in a name? Adding method to the madness
productmarketing
PRO
23
3.6k
Building Adaptive Systems
keathley
43
2.7k
Why You Should Never Use an ORM
jnunemaker
PRO
58
9.5k
Balancing Empowerment & Direction
lara
1
490
10 Git Anti Patterns You Should be Aware of
lemiorhan
PRO
656
60k
How to train your dragon (web standard)
notwaldorf
96
6.1k
It's Worth the Effort
3n
185
28k
Designing Experiences People Love
moore
142
24k
Build The Right Thing And Hit Your Dates
maggiecrowley
37
2.8k
We Have a Design System, Now What?
morganepeng
53
7.7k
"I'm Feeling Lucky" - Building Great Search Experiences for Today's Users (#IAC19)
danielanewman
229
22k
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