Upgrade to Pro — share decks privately, control downloads, hide ads and more …

大規模Webサービス入門 5回目 / Introduction to large scale ...

muttan
August 11, 2017

大規模Webサービス入門 5回目 / Introduction to large scale web service 5

muttan

August 11, 2017
Tweet

More Decks by muttan

Other Decks in Technology

Transcript

  1. ʲྫʳ͸ͯͳΩʔϫʔυʹΑΔϦϯΫ • ݱࡏ͸Common Prefix Searchʢڞ௨઀಄ࣙݕࡧʣͱ Trie໦Λ࢖ͬͯϚονϯά͍ͯ͠Δ • Common Prefix Searchʹ͸,

    Aho-Corasick๏ʢΤΠ ϗʔίϥγοΫʣ΍Double Array TrieͳͲ • ࣗવݴޠॲཧാͩͱԦಓͳํ๏Β͍͠ • Aho-Corasick͸ؤுͬͯௐ΂͍ͯͩ͘͞
  2. Trie໦ͱ͸ t e a n o i n n w

    e keys: tea, ten, to, i, in, inn, we
  3. ୈ2ճʙୈ5ճͷখ·ͱΊ 1. ΪΨόΠτ୯Ґͷσʔλॲཧ
 ςϥ, ϖλόΠτͷσʔλΛѻ͏ʹ͸Ͳ͏͢Δ͔. 2. ϝϞϦॏཁ
 ϝϞϦʹࡌΔͳΒϝϞϦʹ. Ωϟογϡ͕ฉ͖΍͍͢ߏ੒ʹ͢Δ. 3.

    ෼ࢄΛҙࣝͨ͠ӡ༻
 ద੾ͳεΩʔϚͷઃఆ, ύʔςΟγϣχϯά, JOINΛආ͚Δ. 4. ద੾ͳΞϧΰϦζϜͱσʔλߏ଄
 Trie໦, Double Array Trie, Common Prefix Search