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

自然言語処理を支える技術 〜要素技術とPerlの活用〜

hide_o_55
August 31, 2014

自然言語処理を支える技術 〜要素技術とPerlの活用〜

hide_o_55

August 31, 2014
Tweet

Other Decks in Technology

Transcript

  1. ϧʔϧϕʔε • ਓखͰϧʔϧΛఆٛͯ͠ॲཧ͢Δ • ෼໺ʹΑͬͯ͸ݱࡏͰ΋౷ܭֶशϞσϧΑΓߴਫ਼౓ • ௕ॴ • ਓखʹΑΔௐ੔͕Ͱ͖Δ •

    ୹ॴ • ϧʔϧͷϝϯςφϯείετ • ϧʔϧͷ࡞੒ʹઐ໳஌͕ࣝඞཁ • ྫ֎ͷଟ͍υϝΠϯ΁ͷద༻͕ۤख
  2. LOUDS • Trieͷߏ଄ΛϏοτྻͰදݱ • ؆ܿϏοτϕΫτϧΛར༻͢Δ͜ͱͰαΠζΛѹॖͭͭ͠ߴ଎ͳΞΫηε͕Մೳ • ؆ܿϏοτϕΫτϧ͸ҎԼͷૢ࡞Λఏڙ͢Δ • access(i): ϏοτϕΫτϧͷi൪໨ͷ஋Λฦ͢

    • rank(i): ઌ಄͔Βi൪໨·Ͱͷ1(·ͨ͸0)ͷ਺Λฦ͢ • select(i): i൪໨ʹग़ݱ͢Δ1(·ͨ͸0)ͷҐஔΛฦ͢ • ҰఆͷϒϩοΫຖʹ1ͷ਺Λอ࣋ͨ͠rankࣙॻΛར༻͢Δ͜ͱͰrank(i)͸ ఆ਺࣌ؒͰॲཧՄೳ • select(i)͸rankࣙॻͷೋ෼୳ࡧͰO(log n)ͰॲཧՄೳ • Perl͔Β͸Text::Tx(tx-trie), Text::Ux(ux-trie)ɺmarisa- trie(SWIG)౳͕ར༻Մೳ
  3. Shift-Reduce • ࠨ͔Βӈ΁୯ޠΛ̍ݸͣͭॲཧ • QueueͱStackΛར༻ͯ͠ॲཧ • Queue : ະॲཧͷ୯ޠΛ֨ೲ •

    Stack : ॲཧதͷ୯ޠΛ֨ೲ • ֤࣌఺Ͱ 1 ͭͷಈ࡞Λબ୒ • shift: 1 ୯ޠΛΩϡʔ͔ΒελοΫ΁Ҡಈ • reduce ࠨ : ελοΫͷ̍୯ޠ໨͸̎୯ޠ໨ͷ਌ • reduce ӈ : ελοΫͷ̍୯ޠ໨͸̎୯ޠ໨ͷ਌ • ෼ྨثΛ࢖ͬͯͲͷಈ࡞ΛऔΔ͔Λֶश