Fast Succinct Trie

'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ͱ͸ʁ w ৘ใཧ࿦తԼݶʹ͍ۙϝϞϦྔͰ5SJFΛදݱ͢Δσʔλߏ଄ OMHМ 0 O Ϗοτ ‣ Oઅ਺ɺМΞϧϑΝϕοταΠζ
w ʮॱং໦ͷ؆ܿදݱʯ ʮϥϕϧͷ഑ྻʯͰΑ͘දݱ͞ΕΔ w ̏ͭͷ୅දతͳॱং໦ͷ؆ܿσʔλߏ଄ #1 #BMBODFE1BSFOUIFTFT %'6%4 %FQUI'JSTU6OBSZ%FHSFF4FRVFODF -06%4 -FWFM0SEFSFE6OBSZ%FHSFF4FRVFODF w ͪͳΈʹɺ 9#8΍N#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 ໼ాΒॱং໦ͷ؆ܿදݱΛ༻͍ͨτϥΠࣙॻͷධՁ৘ॲશࠃ ࠓͱͳͬͯ͸ ͦ͜·Ͱ໰୊͡Όͳ͍

ઃܭͷϞνϕʔγϣϯ 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 ͨ Θ ʹ ͠ Έ ͨ Θ ͠

- ͨ Θ Θ ͨ ʹ ͠ ͠ Έ )$ 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

- ͨ Θ Θ ͨ ʹ ͠ ͠ Έ )$ 4 ˞ଟগɺ؆ུԽͯ͠·͢ QPT )$<QPT>ͳͷͰ༿ ୳ࡧɿQPT -<QPT>จࣈ ͳQPT ֬ೝɿ)$<QPT>ͳΒͦͷࢠ͸಺෦અ఺ ભҠɿ$IJME1PT QPT 4FMFDU 4 3BOL )$ QPT ͨ Θ ʹ ͠ Έ ͨ Θ ͠

'45ͷͦͷଞͷ޻෉ w -06%4%FOTF4QBSTFͦΕͧΕʹద੾ͳ3BOLࣙॻͷઃܭ w 4*.%ʹΑΔϥϕϧ୳ࡧͷߴ଎Խ w ϓϦϑΣον໋ྩͷ׆༻ 24 ਤ͸࿦จΑΓҾ༻

'45ͷԠ༻ɿ3BOHF2VFSZ'JMUFSJOH w '45͸3BOHF2VFSZ'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

Fast Succinct Trie

Fast Succinct Trie

Shunsuke Kanda

More Decks by Shunsuke Kanda

Other Decks in Research

Featured

Transcript

'BTU4VDDJODU5SJF @kampersanda 7th StringBeginners ঺հ࿦จɿ ;IBOH -JN -FJT "OEFSTFO ,BNJOTLZ

'BTU4VDDJODU5SJF '45 w ೥ͷ4(.0%ͰఏҊ͞Εͨ؆ܿ5SJFදݱ ;IBOHFUBM4V3'1SBDUJDBMSBOHFRVFSZpMUFSJOHXJUI GBTUTVDDJODUUSJFT4(.0% 4VDDJODU3BOHF'JMUFS

5SJFࣙॻ w 5SJFͱҰݴͰݴͬͯ΋ɺٻΊΒΕΔૢ࡞͸͍Ζ͍Ζ w ࠓճ͸؆୯ʹҎԼͷΑ͏ͳૢ࡞͕Ͱ͖Ε͹Α͠ͱ͠·͢ .FNCFS 4 ɿจࣈྻ4͕Ωʔͱؚͯ͠·Ε͍ͯΔ͔ʁ

ͦ΋ͦ΋؆ܿ5SJFͬͯԿʁ 'BTU4VDDJODU5SJF '45 ͱ͸ʁ 5SJFࣙॻͱͯ͠ͷ'45ͷੑೳ͸ʁ

ͦ΋ͦ΋؆ܿ5SJFͬͯԿʁ 'BTU4VDDJODU5SJF '45 ͱ͸ʁ 5SJFࣙॻͱͯ͠ͷ'45ͷੑೳ͸ʁ

؆ܿ5SJFͱ͸ʁ w ৘ใཧ࿦తԼݶʹ͍ۙϝϞϦྔͰ5SJFΛදݱ͢Δσʔλߏ଄ OMHМ 0 O Ϗοτ ‣ Oઅ਺ɺМΞϧϑΝϕοταΠζ

#1 #BMBODFE1BSFOUIFTFT w ֤અ఺Λ։ׅހ(ͱดׅހ)ͷϖΞͰදݱ ਂ͞༏ઌॱͰ໦Λ૸ࠪ ߦ͖ͷ๚໰Ͱ(Λஔ͖ɺؼΓͷ๚໰Ͱ)Λஔ͘ 7

%'6%4 %FQUI'JSTU6OBSZ%FHSFF4FRVFODF w #1ΑΓଟػೳͳׅހྻදݱ ਂ͞༏ઌॱͰ໦Λ૸ࠪ ֤અ఺ʹ͍ͭͯɺͦͷࢠͱಉ͡਺ͷ(ͱ̍ݸͷ)Λஔ͘ ࠷ޙʹઌ಄ʹ(Λஔ͘

-06%4 -FWFM0SEFSFE6OBSZ%FHSFF4FRVFODF w ͜ͷੈͰ΋ͬͱ΋γϯϓϧͳ໦දݱʢྑ͍ҙຯͰʣ ෯༏ઌॱʹ໦Λ૸ࠪ ֤અ఺ʹ͍ͭͯɺͦͷࢠͱಉ͡਺ͷ1ͱ̍ݸͷ0Λஔ͘ ࠷ޙʹઌ಄ʹ10Λஔ͘

؆ܿ5SJFͷϨϏϡʔ 10 ػೳੑ ݕࡧ଎౓ ࣮૷೉౓ #1 ̋ ˚ ೉ %'6%4

ͦ΋ͦ΋؆ܿ5SJFͬͯԿʁ 'BTU4VDDJODU5SJF '45 ͱ͸ʁ 5SJFࣙॻͱͯ͠ͷ'45ͷੑೳ͸ʁ

ઃܭͷϞνϕʔγϣϯ w ࠜͷ෇ۙͷઅ఺ͱ༿ͷ෇ۙͷઅ఺Ͱ͸ੑ࣭΍໾ׂ͕ҧ͏ 12 w ͪͳΈʹɺͦͷΑ͏ͳϞνϕʔγϣϯ͸఻౷తʹ͋Γ·͢ "35ɿઅ఺ͷ࣍਺ʹΑΓద੾ͳσʔλߏ଄Λબ୒ #VSTU5SJF)"5ɿࠜ෇ۙͷઅ఺Λ୯७ͳ഑ྻͰදݱ

-06%4%4ɿೋछྨͷ-06%4Ͱදݱ 13 ਤ͸࿦จΑΓҾ༻ w ࠜ෇ۙ͸ߴ଎ͳ-06%4%FOTF w ༿෇ۙ͸ϝϞϦޮ཰ͷྑ͍-06%44QBSTF

-06%4%FOTF 14 - )$ ͨ Θ ʹ ͠ Έ ͨ

-06%4%FOTF 15 - )$ ͨ Θ ʹ ͠ Έ ͨ

-06%4%FOTF 16 ͨ Θ ʹ ͠ Έ ͨ Θ ͠

-06%4%FOTF 17 ͨ Θ ʹ ͠ Έ ͨ Θ ͠

-06%4%FOTF 18 ͨ Θ ʹ ͠ Έ ͨ Θ ͠

-06%44QBSTF 19 ͨ Θ

-06%44QBSTF 20 ʮΘͨ͠ʯͰݕࡧ

-06%44QBSTF 21 ʮΘͨ͠ʯͰݕࡧ

ͨ Θ ʹ ͠

-06%44QBSTF 23 ʮΘͨ͠ʯͰݕࡧ

'45ͷͦͷଞͷ޻෉ w -06%4%FOTF4QBSTFͦΕͧΕʹద੾ͳ3BOLࣙॻͷઃܭ w 4*.%ʹΑΔϥϕϧ୳ࡧͷߴ଎Խ w ϓϦϑΣον໋ྩͷ׆༻ 24 ਤ͸࿦จΑΓҾ༻

ͦ΋ͦ΋؆ܿ5SJFͬͯԿʁ 'BTU4VDDJODU5SJF '45 ͱ͸ʁ 5SJFࣙॻͱͯ͠ͷ'45ͷੑೳ͸ʁ

'45ͷԠ༻ɿ3BOHF2VFSZ'JMUFSJOH w '45͸3BOHF2VFSZ'JMUFSJOHͷҝͷσʔλߏ଄ͱͯ͠ఏҊ͞Εͨ 26 * $ % . & .

'45ͷੑೳʢ࿦จΑΓҾ༻ʣ w طଘͷ؆ܿ5SJFࣙॻͱൺ΂ͯ 27 Ϗοτ੔਺ΛόΠτจࣈྻͱͯ͠ ϗετ໊Λͻͬ͘Γฦͯ͠ FH DPNHPPMHF!LBOEB UYUSJFγϯϓϧͳ-06%4 1%5ܦ࿏෼ղ

'45ͷੑೳʢ࿦จΑΓҾ༻ʣ w CJUJOUͰ͸-06%4%FOTFͷߩݙ͕େ͖͍ Ұ༷෼෍Ͱੜ੒͞Εͨ੔਺σʔλ ͳͷͰ֤અ఺ͷࢠͷ਺͕ͱͯ΋େ͖͍ 28 CBTFMJOF-06%44QBSTFͷΈ w

5SJFࣙॻɺ࣮૷͠·ͨ͠ 29 w IUUQTHJUIVCDPNLBNQFSTBOEBGBTU@TVDDJODU@USJF

.FNPSZ6TBHF .J# '45 %"354$ 9$%"5

31 ࣮ݧʢ"TLJUJT`TEBUBTFUʣ .FNPSZ6TBHF .J# '45

·ͱΊ w '45͸γϯϓϧͳ-06%4ͳվྑ w ੔਺஋σʔλ͔Β੒ΔΑ͏ͳઅ఺ͷࢠͷ਺͕ͱͯ΋ଟ͍5SJFʹ ରͯ͠͸ɺ-06%4%FOTFͷߩݙ͕ͱͯ΋େ͖͍ 3BOHFRVFSZpMUFSJOHͷͨΊͷσʔλߏ଄ͱͯ͠͸Α͍ w ҰํͰɺࣗવݴޠσʔλͳͲͰ͸طଘͷ5SJFࣙॻͷํ͕ޮ཰͕