৘ใॲཧֶձ‫ڀݚ‬ใࠂ
IPSJ SIG Technical Reportಈతґଘάϥϑͷ 3-gram Λ༻͍࣮ͨߦτϨʔεͷൺֱख๏ϒϠϯωϝϑ Φυϑʔ1,a)ੴඌ ོ1,b)Ҫ্ ࠀ࿠1,c)֓ཁɿϓϩάϥϜͷৄ͍͠ಈ࡞Λཧղ͢ΔͨΊʹɼιϑτ΢ΣΞʹҟͳΔ 2 ͭͷೖྗΛ༩࣮͑ͯߦ͠ɼͦ
ͷ࣮ߦτϨʔεΛൺֱ͢Δख๏͕ఏҊ͞Ε͍ͯΔɽ͔͠͠ɼσόοάΛ໨తͱͨ͠‫ط‬ଘख๏͸ɼ͋Β͔͡Ί෼ੳର৅ͱͳΔม਺΍σʔλߏ଄Λ։ൃऀ͕બ୒͢Δඞཁ͕͋ΓɼϓϩάϥϜͷಈ࡞Λ͜Ε͔Βཧղ͠Α͏ͱ͍͏ஈ֊Ͱར༻͢Δ͜ͱ͸೉͍͠ɽ‫ػ‬ೳͷ࣮૷Ґஔͷ૞ࡧ΍ςετΛ໨తͱͨ͠‫ط‬ଘख๏͸ɼϓϩάϥϜʹৄ͘͠ͳ͘ͱ΋ར༻ՄೳͰ͋Δ͕ɼϓϩάϥϜͷ‫ػ‬ೳͷ࣮૷ʹ౰ͨΔࡉ͔͍ಈ࡞ͷൺֱʹ·Ͱ͸ར༻Ͱ͖ͳ͍ɽͦ͜Ͱຊ‫Ͱڀݚ‬͸ɼJava ϓϩάϥϜͷ 2 ͭͷ࣮ߦτϨʔεؒͷৄࡉͳࠩҟͷҰཡΛ‫͢ࢉܭ‬Δ͜ͱͰɼ෼ੳର৅Λબ୒͠ͳ͘ͱ΋࣮ߦτϨʔεͷৄࡉΛൺֱ͢Δ͜ͱΛՄೳͱ͢Δख๏ΛఏҊ͢Δɽ
۩ମతʹ͸ɼ࣮ߦτϨʔεΛಈతґଘؔ܎ʹैͬͯ 3 ͭͷ໋ྩϒϩοΫΛฒ΂ͨ 3-gram ͷू߹΁ͱม‫׵‬͠ɼͦͷू߹ಉ࢜Λൺֱͯࠩ͠෼Λग़ྗ͢ΔɽఏҊख๏ͷධՁͷͨΊɼDaCapo ϕϯνϚʔΫ ʹऩ࿥͞Ε࣮ͨߦτϨʔεͷൺֱʹద༻͢ΔέʔεελσΟΛߦ͍ɼ࣮ߦτϨʔε͔Βখ͞ͳ 3-gram ͷू߹Λநग़͠ɼൺֱ͕ՄೳͰ͋Δ͜ͱΛ֬ೝͨ͠ɽ

1. ͸͡Ίʹ

ྗΛߦͬͨ৔߹ʹɼͦͷग़ྗΛߦ໋ͬͨྩΛ‫࣮ͯ͠ͱ఺ج‬ߦτϨʔεΛ૎Γɼ࣮ߦ͕ҟͳΔ‫ݪ‬ҼͱͳͬͨೖྗΛಛఆιϑτ΢ΣΞͷอक࡞‫͍͓ͯʹۀ‬ɼ‫ػ‬ೳ௥Ճ΍σόοάɼ͠ɼͦͷೖྗ͕ͲͷΑ͏ͳม਺΍੍‫ޚ‬จΛ‫ܦ‬༝ͯ͠ग़ྗʹςετΛߦ͏ͨΊʹɼ։ൃऀ͸ϓϩάϥϜͷಈ࡞Λཧղ͢Ө‫ڹ‬Λ༩͔͑ͨΛද͢άϥϑ (causal diﬀerence graph) ΛΔඞཁ͕͋ΔɽιʔείʔυͷղੳͷΈͰ͸ಈతଋറ΍ྫ

ग़ྗ͢Δɽ͜ͷख๏Λ࢖͏ͨΊʹ͸ɼ։ൃऀ͸ɼ෼ੳͨ͠

֎ॲཧͳͲͷ࣮ߦ࣌৘ใΛ֫ಘ͠ʹ͍ͨ͘ΊɼϓϩάϥϜ

͍‫ػ‬ೳͷग़ྗ͕มԽ͢ΔΑ͏ͳೖྗΛ͋Β͔͡Ίಛఆ͠ʹԿΒ͔ͷೖྗΛ༩͑ͨͱ͖ʹ࣮ߦ͞ΕΔ໋ྩͷ‫ྻܥ‬ɼ͓ͯ͘͢ඞཁ͕͋ΔɽRelative Debugging[3] ͸ɼ2 ͭͷೖྗͳΘ࣮ͪߦτϨʔε (Execution Trace) ͕ॏཁͳ৘ใ‫ݯ‬ͷʹରͯ͠ϓϩάϥϜΛฒߦ࣮ͯ͠ߦ͠ɼ։ൃऀ͕ࢦఆͨ͠

1 ͭͰ͋Δ [1]ɽ͋Δೖྗʹରͯ͠ಘΒΕΔ୯ಠͷ࣮ߦτσʔλߏ଄ʹ֨ೲ͞Εͨ஋ʹ͕ࠩੜͨ͡λΠϛϯάͰ࣮ߦϨʔεΛ෼ੳ͢Δ͚ͩͰ΋ͲͷΑ͏ʹॲཧ͕࣮ߦ͞Ε͔ͨΛҰ࣌ఀࢭ͠ɼͦͷ৘ใΛ։ൃʹ஌ΒͤΔɽ͜ͷख๏΋ɼΛཧղ͢Δ͜ͱ͸ՄೳͰ͋Δ͕ɼҟͳΔ 2 ͭͷೖྗΛ༩͑͋Β͔͡Ίιʔείʔυʹର͢ΔཧղΛਐΊɼ‫͖΂͢࡯؍‬ͨ৔߹΍ҟͳΔ࣮ߦ‫Ͱڥ؀‬ಉҰͷೖྗΛ༩͑ͨ৔߹ͱ͍ͬ

σʔλߏ଄Λ஌͍ͬͯΔඞཁ͕͋ΔɽͨΑ͏ʹɼҟͳΔ৚݅ͰಘΒΕΔ 2 ͭͷ࣮ߦτϨʔεΛൺຊ‫Ͱڀݚ‬͸ɼ։ൃऀ͕୯Ұͷ Java ϓϩάϥϜ͔Βऔಘֱ͢Δ͜ͱͰɼೖྗͱॲཧͷؔ܎ͳͲɼ‫ػ‬ೳͷ࣮૷Λৄ͠

ͨ͠ 2 ͭͷ࣮ߦτϨʔε͔Βɼͦͷಈ࡞ͷࠩҟΛྻ‫ͯ͠ڍ‬

͘ཧղ͢Δ͜ͱ͕ՄೳʹͳΔɽ

։ൃऀʹఏࣔ͢Δख๏ΛఏҊ͢Δɽ͜ΕʹΑΓɼ1 ͭͷ‫ػ‬͔͠͠ɼ࣮ߦτϨʔεͷৄࡉΛൺֱ͢Δ‫ط‬ଘ‫ڀݚ‬͸ɼσೳʹҟͳΔೖྗΛ༩࣮͑ͯߦͨ͠৔߹ʹɼͲͷ໋ྩͰɼͲ

όοάΛओͳ໨తͱ͓ͯ͠Γɼ͋Β͔͡Ί෼ੳର৅ͱͳΔ

ͷΑ͏ͳ੍‫ޚ‬ϑϩʔɼσʔλϑϩʔʹؔ͢Δҧ͍͕ੜͨ͡

ม਺΍σʔλߏ଄Λ։ൃऀ͕બ୒Ͱ͖Δ͜ͱ͕લఏ৚݅

ͷ͔Λ։ൃऀʹఏࣔ͢Δɽ2 ͭͷ࣮ߦτϨʔεͷൺֱ‫ج‬४ͱͳ͍ͬͯΔɽͦͷͨΊɼϓϩάϥϜͷಈ࡞Λ͜Ε͔Βཧͱͯ͠ɼ࣮ߦ͞Ε໋ͨྩؒͷಈతґଘؔ܎Λ༻͍Δɽͨͩղ͠Α͏ͱ͍͏ஈ֊Ͱར༻͢Δ͜ͱ͕೉͍͠ɽͨͱ͑͹͠ɼಈతϓϩάϥϜεϥΠγϯά [4] ʹར༻͞ΕΔΑ͏ͳಈ

Diﬀerential Slicing[2] ͸ɼ2 ͭͷ࣮ߦ͕ͦΕͧΕҟͳΔग़తґଘάϥϑ͸ɼ࣮ߦτϨʔεͷྔʹൺྫͯͦ͠ͷαΠζ
͕૿Ճ͢ΔͨΊ௚઀ൺֱ͢Δ͜ͱ͸‫࣮ݱ‬తͰ͸ͳ͍ɽͦ͜

1

a)
b)
c)

େࡕେֶେֶӃ৘ใՊֶ‫ڀݚ‬ՊGraduate School of Information Science and Technology, Osaka University, Suita, Osaka 565-0871, Japanb-odkhuu@ist.osaka-u.ac.jp
ishio@ist.osaka-u.ac.jp
inoue@ist.osaka-u.ac.jp

c 2012 Information Processing Society of JapanͰɼຊ‫Ͱڀݚ‬͸ϓϩάϥϜதͷόΠτίʔυ໋ྩΛϒϩοΫ୯ҐͰ௖఺ͱͯ͠ɼͦΕΒΛ઀ଓ͢Δಈతґଘลͷ‫ܦ‬࿏Λநग़͠ɼґଘؔ܎Ͱ઀ଓ͞Εͨ 3 ͭͷ໋ྩϒϩοΫͷฒͼʢ3-gramʣͷू߹΁ͱ෼ղ͢Δɽ2 ͭͷ࣮ߦτϨʔεͦ1৘ใॲཧֶձ‫ڀݚ‬ใࠂ
IPSJ SIG Technical ReportΕͧΕ͔ΒಘΒΕͨू߹Λൺֱ͢Δ͜ͱͰɼ֤࣮ߦτϨʔ

Λ 1 ͭͷ࣮ߦτϨʔεͱͯ͠‫ه‬࿥Ͱ͖Ε͹ɼͦͷࠩ෼ʹ౰εʹ‫ݻ‬༗ͷ໋ྩؒͷಈతґଘؔ܎Λऔಘ͠ɼґଘؔ܎ͷࠩ

ͨΔ࣮ߦτϨʔε͕໨తͷ‫ػ‬ೳʹؔ܎͢Δͱ͍͏ߟ͑ํͰ

ҟΛ։ൃऀ͕֬ೝͰ͖ΔΑ͏ʹ͢Δɽ

͋Δɽ2 ͭͷ࣮ߦτϨʔεʹ‫·ؚ‬ΕΔ‫ػ‬ೳͷରԠؔ܎͕े

ఏҊख๏ͷ༗ޮੑΛ‫͢ূݕ‬ΔͨΊʹɼఏҊख๏Λ DaCapo

෼ʹ͋Δ৔߹͸ɼCornelissen Βͷख๏ [10] ΍ Jonas ΒͷϕϯνϚʔΫ [5] ʹऩ࿥͞Εͨ batikɼfop ͱ͍͏ 2 ͭͷΞख๏ [11] Ͱ࣮ߦτϨʔεͷσʔλͷରԠؔ܎ΛՄࢹԽ͠ɼ

ϓϦέʔγϣϯʹద༻͠ɼϓϩάϥϜͷಈ࡞Λཧղ͢Δέʔ࣮ߦτϨʔεͷதͷಛఆͷ෦෼‫͚ͩʹྻܥ‬஫໨͢Δ͜ͱ΋εελσΟΛߦͬͨɽϕϯνϚʔΫʹ͸ΞϓϦέʔγϣϯՄೳͰ͋Δɽͨͩ͠ɼ͜ΕΒͷख๏Ͱ͸ɼ࣮ߦτϨʔεಉ͝ͱʹ small, default, large ͱ͍͏ 3 छྨͷ࣮ߦτϨʔε࢜ͷେ·͔ͳରԠؔ܎ΛऔΔ͜ͱΛॏࢹ͍ͯ͠ΔͨΊɼ֤͕༻ҙ͞Ε͍ͯͨ͜ͱ͔Βɼͦͷ͏ͪ small ͱ default ͷ‫ػ‬ೳͷதͷࡉ͔͍ॲཧͷϨϕϧͰͷҧ͍ΛՄࢹԽ݁Ռ͔Β૊Λൺֱ͠ɼϓϩάϥϜ࣮ߦ࣌ͷग़ྗϝοηʔδͳͲ͔Β‫ݟ‬෼͚Δ͜ͱ͸೉͍͠ɽ‫ظ‬଴͞ΕΔࠩҟ͕ɼ࣮ߦτϨʔεͰͲͷΑ͏ͳҧ͍ͱͯ͠‫ݱ‬ΕΔ͔Λ෼ੳͨ͠ɽ

Ϣʔβͷૢ࡞ཤྺͳͲɼଟ਺ͷ࣮ߦτϨʔε͕ಘΒΕΔ
৔߹ʹɼྨࣅ࣮ͨ͠ߦτϨʔεΛ‫ݕ‬ग़͢Δख๏΋ఏҊ͞Εຊ࿦จͷߏ੒͸࣍ͷ௨ΓͰ͋Δɽ·ͣɼ2 ষͰ‫ڀݚ‬ͷഎ

͍ͯΔɽMiranskyy[12] Β͸‫ݱ‬৔ͳͲͰूΊͨෳ਺ͷ࣮ߦ‫͍ͯͭʹܠ‬ड़΂Δɽ3 ষͰఏҊख๏ʹ͍ͭͯɼ4 ষͰέʔτϨʔεಉ࢜Λൺֱ͠ɼ‫ج‬४ͱͳΔ࣮ߦτϨʔεʹྨࣅ౓εελσΟʹ͍ͭͯઆ໌͢Δɽ࠷‫ ʹޙ‬5 ষͰຊ‫ڀݚ‬ͷ·ͱ͕ߴ͍࣮ߦτϨʔεΛϑΟϧλϦϯά͢Δख๏ΛఏҊͯ͠Ίͱࠓ‫ޙ‬ͷ՝୊ʹ͍ͭͯड़΂Δɽ

͍Δɽ࣮ߦτϨʔεൺֱ͸ɼൺֱ‫ج‬४Λ͍͔ͭ͘ͷஈ֊ʹ

2. എ‫ܠ‬2.1 ࣮ߦτϨʔεͷൺֱ࣮ߦτϨʔεͱ͸ϓϩάϥϜʹԿΒ͔ͷೖྗΛ༩͑ͨͱ͖ʹ࣮ߦ͞ΕΔ໋ྩͷ‫͋Ͱྻܥ‬Δɽਖ਼֬ͳಈ࡞͕෼͔Β෼͚ɼൺֱ‫ج‬४͕ૈ͍Ϩϕϧ͔Βࡉ͔͍Ϩϕϧ·Ͱൺֱ͍͖ͯ͠ɼࣅ͍ͯͳ͍΋ͷΛআ‫͍ͯ͘͠ڈ‬ɽ͜ͷख๏͸ɼෳ਺ͷτϨʔε͔Βྨࣅ࣮ͨ͠ߦτϨʔεͷ૊Λநग़͢Δ͜
ͱ͸Ͱ͖Δ͕ɼ࣮ߦτϨʔεಉ࢜ͷৄࡉͳൺֱͦͷ΋ͷΛҙਤٕͨ͠ज़Ͱ͸ͳ͍ɽͳ͍ϓϩάϥϜʹରͯ͠ɼC ‫͋Ͱޠݴ‬Ε͹ printf ؔ਺ɼ࣮ߦτϨʔεͷΘ͔ͣͳҧ͍Λ۠ผ͢Δͱ͍͏‫Ͱ఺؍‬͸ɼ

Java Ͱ͋Ε͹ System.out.println ϝιουͷ‫ͼݺ‬ग़͠ग़ྗͷҧ͍Λ‫ͦͯ͠ͱ఺ج‬ͷ‫ݪ‬ҼΛ෼ੳ͢Δ DiﬀerentialΛຒΊࠐΜͰϓϩάϥϜͷ࣮ࡍͷ໋ྩͷ࣮ߦॱংΛը໘ʹ

Slicing[2] ΍ɼฒߦ࣮ͯ͠ߦ͞ΕΔϓϩάϥϜʹԿΒ͔ͷࠩग़ྗ֬͠ೝ͢Δ͜ͱ͸ɼσόοάʹ͓͚Δ‫ج‬ຊςΫχοΫ

͕ੜͨ࣌͡఺Λ‫ݕ‬஌͢Δ Relative Debugging[3] ͕ఏҊ͞

ͷ 1 ͭͰ͋Δ [6]ɽϓϩάϥϜཧղ΍σόοάʹ͓͍ͯ͸ɼΕ͍ͯΔɽ͜ΕΒͷٕज़͸ϝϞϦͷൺֱ΍ಈతґଘؔ܎ͷ

Omniscient Debugging [7] ͱ‫ݺ‬͹ΕΔɼม਺ͷ࣮ࡍͷ஋ͷൺֱʹΑͬͯৄࡉͳൺֱΛՄೳͱ͢ΔҰํͰɼࠩҟ͕ੜ͡‫ྻܥ‬΍৚݅෼‫ذ‬ͷ݁Ռ͕ࢀরՄೳͳ࣮ߦτϨʔεΛ༻͍Δͨঢ়ଶ΍‫ݪ‬ҼΛௐ΂͍ͨσʔλߏ଄΍ग़ྗΛ։ൃऀ͕͋Βख๏͕༗ޮͰ͋Δͱ‫ݴ‬ΘΕ͍ͯΔ [8]ɽҰํͰɼͦͷΑ͏ͳ͔͡Ίࢦఆ͠ͳ͚Ε͹ͳΒͳ͍ͨΊɼͲ͜ʹࠩҟ͕ੜ͡Δ

ৄࡉͳ࣮ߦτϨʔε͸ϓϩάϥϜͷ࣮ߦ։͔࢝Βऴྃʹࢸͷ͔Λ͜Ε͔Βௐ΂Δͱ͍͏ஈ֊Ͱ͸ར༻͢Δ͜ͱ͕Ͱ͖

Δ·Ͱͷ‫ܦ‬࿏Λอଘ͢ΔͨΊɼҰൠʹ͸‫ڊ‬େͳσʔλͱͳͳ͍ɽΔɽͨͱ͑͹ Omniscient Debugging ͱͯ͠࠷ॳʹࣔ͞Ειϑτ΢ΣΞςετͷ෼໺Ͱ͸ɼϓϩάϥϜʹ༩͑Δೖ࣮ͨ૷ [7] Ͱ͸ɼ2 ϚΠΫϩඵ͝ͱʹϓϩάϥϜͷϝϞϦͷ

ྗɼ͢ͳΘͪςετέʔεΛมԽͤͨ͞ͱ͖ɼ৽͍͠ςεঢ়ଶͷίϐʔΛอଘ͓ͯ͘͜͠ͱͰϓϩάϥϜͷ೚ҙͷ࣌τέʔε͕ࠓ·Ͱͷςετέʔεʹ‫·ؚ‬Ε͍ͯͳ͔ͬͨॲ

఺Ͱͷঢ়ଶʹ૎Δ͜ͱΛՄೳͱ͕ͨ͠ɼΘ͔ͣ 20 ඵͷ࣮ߦཧΛ࣮ߦ͔ͨ͠Ͳ͏͔ΛΧόϨοδͷมԽʹΑͬͯ൑அ͢

Ͱ 32 Ϗοτ‫Ͱػࢉܭ‬ར༻Մೳͳ 2GB ͷϝϞϦΛ࢖͍੾ͬΔ [13]ɽεςʔτϝϯτΧόϨοδ͸࣮ߦτϨʔεʹ‫·ؚ‬ͨ͜ͱΛใࠂ͍ͯ͠Δɽ͜ͷΑ͏ͳ‫ڊ‬େͳσʔλ͔ΒɼϓΕͨιʔείʔυ্ͷ໋ྩͷू߹ΛɼϒϥϯνΧόϨοδ

ϩάϥϜͷߏ଄΍ಈ࡞Λৄ͘͠஌Βͳ͍ঢ়ଶͰɼ։ൃऀʹ͸࣮ߦτϨʔε͕௨աͨ͠৚݅෼‫ذ‬ͷू߹Λɼdef-use Χόͱͬͯ‫ڵ‬ຯͷ͋Δॲཧͷ಺༰Λ෼ੳ͢Δ͜ͱ͸೉͍͠ɽϨοδ͸࣮ߦτϨʔεதʹग़‫ͨ͠ݱ‬ม਺ͷ୅ೖͱࢀরͷ૊࣮ߦτϨʔεͷൺֱʹΑͬͯɼ‫ڵ‬ຯͷ͋Δॲཧͷ࣮ߦΛू߹ͱͯ͠ൺֱ͢Δɽ͜ΕΒͷΧόϨοδ‫ج‬४΋·ͨɼʹ͚ͩ஫໨͢Δख๏͕ఏҊ͞Ε͍ͯΔɽEisenbarth Β [9]࣮ߦͷࠩҟΛൺֱ͢Δख๏ͱ‫ݟ‬Δ͜ͱ͕Ͱ͖Δ͕ɼຊ‫ڀݚ‬͸ɼ࣮ߦτϨʔεʹ‫·ؚ‬Εͨ‫ػ‬ೳΛ։ൃऀ͕ྻ‫͖Ͱڍ‬ΔͱͰ͸ґଘؔ܎ͷ‫ܦ‬࿏Λ࢖༻͓ͯ͠Γɼ͜ΕΒͷΧόϨοδ

͖ɼෳ਺ͷ࣮ߦτϨʔεͰ࣮ߦ͞Εͨؔ਺΍ϝιουͷू‫ج‬४ΑΓ΋‫͍͠ݫ‬৚݅ͰൺֱΛߦ͏ɽ߹ͷࠩΛɼ‫ػ‬ೳͷࠩʹରԠ͚ͮΔ͜ͱͰɼ֤‫ػ‬ೳͱ࣮ߦτϨʔεͱͷରԠؔ܎Λ‫ٻ‬ΊΔख๏Λఆٛͨ͠ɽϓϩάϥϜ

2.2 ಈతґଘάϥϑΛ‫ى‬ಈͯͦ͠ͷ࣮ߦΛߦ͔ͬͯΒϓϩάϥϜΛऴྃ͢Δͱຊ‫Ͱڀݚ‬͸ɼ2 ͭͷ࣮ߦτϨʔε͔ΒಘΒΕͨಈతґ͍͏Ұ࿈ͷಈ࡞Λ 1 ͭͷ࣮ߦτϨʔεͱͯ͠‫ه‬࿥͠ɼϓϩଘؔ܎ͷൺֱΛߦ͏ɽಈతґଘؔ܎ͱ͸ɼ͋Δ໋ྩͰ୅άϥϜΛ‫ى‬ಈ͙ͯ͢͠ʹϓϩάϥϜΛऴྃ͢Δͱ͍͏ಈ࡞

ೖ͞Εͨม਺ͷ஋͕ผͷ໋ྩͰ࢖༻͞Εͨͱ͍͏Α͏ʹɼc 2012 Information Processing Society of Japan

2৘ใॲཧֶձ‫ڀݚ‬ใࠂ
IPSJ SIG Technical ReportϓϩάϥϜͷ࣮ߦதʹ࣮ࡍʹൃੜͨ͠Ө‫ڹ‬ͷ͜ͱͰ͋Δɽ

Zhang[14] ΒͷఆٛʹΑΔͱɼ͋Δ໋ྩ s ͷ i ճ໨ͷ࣮ߦ͕‫ه‬ԱҬͷू߹ U ʹ֨ೲ͞Εͨ஋Λࢀরͯ͠ D ͷ஋Λఆٛͨ͜͠ͱΛ si (U, D) Ͱද͢ͱ͢Δͱɼσʔλґଘؔ܎ɼ੍‫ޚ‬ґଘؔ܎͸ͦΕͧΕ࣍ͷΑ͏ͳ‫Ͱܗ‬༩͑ΒΕΔɽσʔλґଘؔ܎ pi (Up , Dp ) ͱ qj (Uq , Dq ) ʹ͓͍ͯɼUq ͱ

Dp ͕‫ڞ‬௨ཁૉΛ 1 ͭҎ্‫ؚ‬Ήͱ͖ɼpi (Up , Dp ) ͔Β
qj (Uq , Dq ) ΁σʔλґଘؔ܎͕ଘࡏ͢Δɽ੍‫ޚ‬ґଘؔ܎ ͋Δ໋ྩͷ࣮ߦ pi (Up , Dp ) Ͱ‫ٻ‬ΊΒΕͨ஋͕ qj (Uq , Dq ) Λ࣮ߦ͢Δ͔Ͳ͏͔ͷ৚݅෼‫͞༻࢖ʹذ‬Εͨͱ͖ɼpi (Up , Dp ) ͔Β qj (Uq , Dq ) ΁੍‫ޚ‬ґଘؔ܎͕ଘࡏ͢Δɽ

qj Ͱ࢖༻ͨ͠ม਺ͷ஋͕ܾ·ͬͨཧ༝ɼqj ͕࣮ߦ͞Εͨཧ༝Λ஌Γ͍ͨ৔߹ʹ͸ɼqj ͔Β pi ΁ͱґଘؔ܎Λ૎͍ͬͯ͘͜ͱʹͳΔ [8]ɽຊ‫Ͱڀݚ‬͸ɼಈతґଘؔ܎ͷ‫ܦ‬࿏͕෦෼తʹ౳͍͠ͱ͍͏͜ͱ͔Βɼͦͷ‫ࢉܭ‬ͷखॱ͕෦෼తʹ

1:
2:
3:
4:
5:
6:

public static void main(String[] args) {int N = Integer.parseInt(args[0]);int sum = 0;
for (int i=1; i<=N; i++) {sum = sum + i;}
System.out.println(sum);}ਤ 1ϓϩάϥϜྫ

1: $r = Integer.parseInt(args[0]);2: int N = $r;
3: int sum = 0;
4: int i = 1;
5: if (i<=N) goto 6; else goto 9;
6: sum = sum + i;
7: i++;
8: goto 5;
9: System.out.println(sum);ਤ 2 ϒϩοΫ୯Ґʹม‫ͨ͠׵‬ϓϩάϥϜ

౳͍͜͠ͱΛ‫ظ‬଴͍ͯ͠Δɽ

3. ఏҊख๏

औΓͷ݁ՌͳͲΛ‫ؚ‬ΜͰ͓ΓɼϓϩάϥϜͷ࣮ߦ࣌ঢ়ଶͷଟ͘Λ࠶‫͖Ͱݱ‬Δඇৗʹৄࡉͳ΋ͷͰ͋Δɽ

ຊ‫Ͱڀݚ‬͸ɼJava ϓϩάϥϜͷ୯ҰͷόʔδϣϯΛ 2ճɼҟͳΔೖྗͰ࣮ߦͯ͠ಘΒΕ࣮ͨߦτϨʔεΛൺֱ͠ɼ

3.1 ໋ྩͷϒϩοΫΛ୯Ґͱ͢ΔϓϩάϥϜͷද‫ݱ‬ͦͷࠩ෼Λநग़͢Δख๏ΛఏҊ͢Δɽ۩ମతʹ͸ɼ֤࣮ߦJava ϓϩάϥϜͷιʔείʔυ͸ɼίϯύΠϧ͞ΕΔͱτϨʔε͔ΒಘΒΕΔಈతґଘؔ܎ΛόΠτίʔυ໋ྩͷଟ਺ͷόΠτίʔυ໋ྩʹ෼ղ͞ΕΔɽͨͱ͑͹ਤ 1 ͸ɼϒϩοΫΛ௖఺ͱͨ͠ಈతґଘάϥϑͱΈͳͯ͠ɼಈతґҾ਺ͱͯ͠౉͞Εͨࣗવ਺ N ʹରͯ͠ 1 ͔Β N ·Ͱͷ࿨Λଘάϥϑʹ͓͚Δ‫ܦ‬࿏Ͱ໋ྩΛ઀ଓͨ͠ 3-gram ͷू߹Λग़ྗ͢ΔϓϩάϥϜͰ͋Δ͕ɼιʔείʔυͱͯ͠͸ 6 ߦ

நग़͢Δɽ2 ͭͷ࣮ߦτϨʔε͔Β‫ݸ‬ผʹऔಘͨ͠ 3-gramͰ͋ͬͯ΋ 1 ߦʹෳ਺ͷॲཧ͕‫·ؚ‬Ε͍ͯΔɽͨͱ͑͹ 3ू߹ͷ‫ڞ‬௨ू߹ɼࠩू߹Λɼ࣮ߦτϨʔεʹ͓͚Δґଘؔߦ໨ͷ for จ͸ɼม਺ i ͷॳ‫ظ‬Խͱɼi ͱ N ͷൺֱ݁Ռʹ܎ͷࠩ෼ͱͯ͠ग़ྗ͢Δɽ

ΑΔ৚݅෼‫ذ‬ɼϧʔϓΛ 1 पͨ͠ͱ͖ͷ i ͷ஋ͷ૿Ճͱ͍ϓϩάϥϜͰ͸‫܁‬Γฦ͠จͷ࣮ߦճ਺͕ҟͳΔ৔߹͕ඇ͏ 3 ͭͷॲཧ͔Βߏ੒͞Ε͍ͯΔɽ

ৗʹଟ͍ͨΊɼ୯७ʹ໋ྩͷ‫Ͳͳྻܥ‬Λͦͷ··ൺֱ͢Διʔείʔυ্ͷจͦͷ··Ͱ͸໋ྩͷ۠੾Γͱͯ͠͸ͱɼϧʔϓͷ࣮ߦճ਺͕ҟͳΔ৔߹ͳͲʹੜ͡Δ໋ྩͷ࣮େ͖͗͢Δ͕ɼͦͷҰํͰόΠτίʔυ͸ඇৗʹࡉ໋͔͍ߦճ਺ͷ͕ࠩओཁͳࠩͱͯ͠நग़͞Εͯ͠·͏ɽͨͱ͑͹ɼྩ͔ΒͳΔɽͨͱ͑͹ɼਤ 1 ͷ 2 ߦ໨ʹ͋Δม਺ sum ͷॳjava.io.FileOutputStream Ϋϥε͸ɼσʔλྻΛϑΝΠ‫ظ‬Խ͸ɼఆ਺ 0 Λ Java Ծ૝ϚγϯͷΦϖϥϯυελοΫ

ϧʹॻ͖ग़ͨ͢Ίʹɼ಺෦Ͱ 1 όΠτͣͭσʔλΛॻ͖ग़ʹϩʔυ͢Δ໋ྩʢICONST_0ʣͱɼΦϖϥϯυελοΫ্͢ॲཧΛߦ͍ͬͯΔɽͦͷͨΊɼ͜ͷΫϥεͷ࣮ߦτϨʔͷ஋ΛϩʔΧϧม਺ʹ֨ೲ͢Δ໋ྩʢISTOREʣʹΑ࣮ͬͯεΛ෼ੳ͠Α͏ͱ͢ΔͱɼϑΝΠϧʹॻ͖ग़ͨ͠σʔλྻ‫͞ݱ‬ΕΔɽ໋ྩ୯ҐͰಈతґଘؔ܎ͷղੳΛߦ͏͜ͱ΋Մͷ௕͕ͦ͞ͷ··࣮ߦτϨʔεʹ͓͚Δࠩͱͯ͠‫ݱ‬ΕΔɽ

ೳͰ͋Δ͕ɼఆ਺ͷಡΈग़͠ͱ֨ೲͱ͍͏໋ྩͷؒʹ͸৚͜ͷΑ͏ͳ࣮ߦτϨʔεͷࠩ෼৘ใ͸ɼϧʔϓ಺෦Ͱͷॲ݅෼‫͕ذ‬ೖΓࠐΉ͜ͱ΋ͳ͘ɼόΠτίʔυ͚͔ͩΒ੩తཧͷ࣮ߦʹ͸΄ͱΜͲมԽ͕ͳ͍ͱ͍͏఺Ͱɼ։ൃऀʹʹͦͷґଘؔ܎͕֬ఆ͢Δ͜ͱ͔Βɼಈతґଘؔ܎ͷ୯Ґͱͬͯ༗༻Ͱ͸ͳ͍ɽͦ͜Ͱɼґଘؔ܎ͷ෦෼తͳ‫ܦ‬࿏ͷͱͯ͠͸খ͗͢͞Δͱߟ͑ΒΕΔɽ

ू߹ͱͯ͠ද‫͢ݱ‬Δ͜ͱͰɼ࣮ߦճ਺ͷ‫ࠩͳີݫ‬Λൺֱʹ࣋ͪࠐ·ͳ͍Α͏ʹͨ͠ɽຊ‫Ͱڀݚ‬͸ɼಈతґଘؔ܎Λ‫ٻ‬ΊΔ୯Ґͱͯ͠ɼόΠτίʔυ໋ྩͷϒϩοΫͱ͍͏֓೦Λಋೖ͢ΔɽόΠτίʔఏҊख๏͸ಈతґଘάϥϑ͕‫͖Ͱࢉܭ‬Ε͹೚ҙͷ࣮ߦτυ໋ྩͷϒϩοΫ͸ɼόΠτίʔυ໋ྩͷྻͱͯ͠ද‫͞ݱ‬Ϩʔεʹରͯ͠ద༻ՄೳͰ͋Δ͕ɼຊ‫ڀݚ‬ͷ࣮૷ʹ͓͍ͯΕͨ Java ͷϝιουΛɼҎԼͷ‫ج‬४Ͱ۠੾ͬͯಘΒΕΔ

͸ REMViewer [15] ͷ࣮ߦτϨʔεΛ࢖༻ͨ͠ɽ͜ͷ࣮ߦ໋ྩͷ෦෼ྻͰ͋ΔɽτϨʔε͸ɼJava ϓϩάϥϜͷόΠτίʔυ୯ҐͰͷ໋ྩ• ϝιουͷઌ಄͸ɼϒϩοΫͷ։࢝Ͱ͋Δɽͷ࣮ߦ‫ͱྻܥ‬ɼϩʔΧϧม਺ͷঢ়ଶɼϑΟʔϧυ΍഑ྻͷ• ͋Δ໋ྩͷऴྃ࣌ʹΦϖϥϯυελοΫ͕ۭͰ͋ΕಡΈॻ͖ɼϝιου‫ͼݺ‬ग़͠ʹΑΔ֎෦γεςϜͱͷ΍Γ͹ɼͦͷ໋ྩ͸ϒϩοΫͷऴ୺Ͱ͋Γɼ࣍ͷ໋ྩ͔Βc 2012 Information Processing Society of Japan

3৘ใॲཧֶձ‫ڀݚ‬ใࠂ
IPSJ SIG Technical Report

1_1

4_1

3_1

6_1

1_1

2_1

4_1

3_1

5_1

7_1

8_1

9_1

6_1

5_1

7_1

5_2

8_1

5_2

d_9

ਤ 3

2_1

6_2

7_2

8_2

N=1 Ͱਤ 1 ͷϓϩάϥϜΛ࣮ߦͨ͠ͱ͖ͷϒϩοΫؒͷಈత
9_1

ґଘؔ܎

৽͍͠ϒϩοΫΛ։࢝͢Δɽ

5_3

d_9

• ϝιου‫ͼݺ‬ग़໋͠ྩ͸ɼΦϖϥϯυελοΫͷঢ়ଶʹؔΘΒͣɼϒϩοΫͷऴ୺Ͱ͋Γɼ࣍ͷ໋ྩ͔Β৽͍͠ϒϩοΫΛ։࢝͢Δɽਤ 4

N=2 Ͱਤ 1 ͷϓϩάϥϜΛ࣮ߦͨ͠ͱ͖ͷϒϩοΫؒͷಈతґଘؔ܎όΠτίʔυ໋ྩ͸ɼ͢΂ͯͷ৚݅෼‫ذ‬Λ IFɼGOTO ໋ྩʹม‫ͨ͠׵‬ঢ়ଶͱͳ͓ͬͯΓɼιʔείʔυͷ 1 จͷத• ϝιου‫ͼݺ‬ग़͠ઌ͕࣮ߦτϨʔεͷ‫؍‬ଌൣғ֎Ͱ͋Ͱͷσʔλͷ΍ΓऔΓʹΦϖϥϯυελοΫΛ࢖༻͍ͯ͠

Δͱ͖͸ɼϝιου‫ͼݺ‬ग़͠ͷҾ਺͸ɼ໭Γ஋ʹର͠

ΔɽͦͷͨΊɼ͜ͷ۠੾Γͷ৚݅͸ɼਤ 1 ͷϓϩάϥϜΛɼͯಈతσʔλґଘؔ܎͕͋Δͱߟ͑Δɽ

ਤ 2 ͷΑ͏ͳ‫ʹࣜܗ‬ม‫͢׵‬Δ͜ͱʹ૬౰͢Δɽਤ 2 ͷ 1 ߦ• ੍‫ޚ‬ґଘؔ܎͸ɼόΠτίʔυ্Ͱ੩తʹಘΒΕΔґ

໨ʹ͓͚Δม਺ $r ͸ɼΦϖϥϯυελοΫʹ֨ೲ͞ΕΔ

ଘؔ܎ͱ໋ྩͷ࣮ߦॱংΛซ༻ͯ͠‫ٻ‬ΊΔɽ۩ମతʹ໭Γ஋Λද‫͍ͯ͠ݱ‬Δɽ͜ͷ෼ղʹΑͬͯɼ1 ϒϩοΫͷ

͸ɼϒϩοΫ p ͔ΒϒϩοΫ q ʹରͯ͠৚݅෼‫ʹذ‬தͰ͸ߴʑ 1 ճ͔͠ϝιουΛ‫ͼݺ‬ग़͞ͳ͍͜ͱʹͳΓɼΑΔ੩త੍‫ޚ‬ґଘؔ܎͕ଘࡏ͢Δͱ͖ɼ͋Δ q ͷ࣮ߦϝιου‫ͼݺ‬ग़ؒ͠ͷґଘؔ܎͕໌֬ʹϒϩοΫؒͷґଘ

qj ͸ɼͦͷ࣮ߦʹ࠷΋͍ۙ pi ͷ࣮ߦʹ੍‫͞ޚ‬Ε͍ͯؔ܎ʹ൓ө͞ΕΔΑ͏ʹͳΔɽ·ͨɼਤ 2 ͷྫʹ͸‫·ؚ‬ΕΔͱΈͳ͢ [16]ɽ

͍ͯͳ͍͕ɼෳ਺ͷ৚݅Λ࿦ཧԋࢉࢠͰ૊Έ߹Θͤͨ if• else અΛ࣋ͨͳ͍ if จͰ͸ɼۭͷ else અ͕͋Δ΋จ΋ɼ‫ݸ‬ผͷ৚݅ʹରԠ͢Δ৚݅෼‫ྩ໋ذ‬Λऴ୺ͱ͢ΔϒͷͱΈͳ͠ɼ৚݅෼‫ذ‬ͷ݁Ռ͕Ͳ͏ͳͬͯ΋ɼඞͣ 1ϩοΫͷ૊Έ߹Θͤʹม‫͞׵‬ΕΔɽ

ͭಈత੍‫ޚ‬ґଘ௖఺Λग़‫ͤ͞ݱ‬Δɽಈతσʔλґଘؔ܎ɼಈత੍‫ޚ‬ґଘؔ܎͸ɼpi → qj ͷΑ

3.2 ϒϩοΫΛ௖఺ͱͨ͠ಈతґଘؔ܎͏ʹ௖఺ؒͷลͱͯ͠ද‫͞ݱ‬ΕΔɽྫͱͯ͠ɼਤ 1 ͷϓϩಈతґଘؔ܎ͷ֓೦͸ 2.2 અʹ‫ه‬ड़ͨ͠௨ΓͰ͋Δ͕ɼ

άϥϜΛ N=1, 2 Ͱ࣮ߦͨ͠ͱ͖ʹಘΒΕΔಈతґଘؔ܎ຊ‫Ͱڀݚ‬͸௖఺ͱͯ͠ϒϩοΫ p ͷ i ճ໨ͷ࣮ߦ pi Λ࢖ΛάϥϑͰද‫ͨ͠ݱ‬΋ͷΛͦΕͧΕਤ 3ɼਤ 4 ʹࣔ͢ɽϒ༻͠ɼϒϩοΫͷ֤࣮ߦͷؒͰͷґଘؔ܎ͱͯ͠ҎԼͷؔϩοΫͷ൪߸͸ਤ 2 ʹରԠ͓ͯ͠ΓɼਤதͰ͸ pi Λ p_i

܎Λ༻͍Δɽ

ͷ‫Ͱࣜܗ‬ද‫͍ͯ͠ه‬Δɽ·ͨɼ௖఺ d_9 ͸ɼ৚݅෼‫ذ‬ઌͷ• σʔλґଘؔ܎ͷఆٛʹ͓͍ͯɼD, U ʹ͸ϩʔΧϧ໋ྩϒϩοΫ 9 ੍͕‫ޚ‬ґଘؔ܎ʹͳ͍͕ɼ৚݅෼‫ذ‬ͷํม਺ɼϑΟʔϧυɼ഑ྻɼϝιου‫ͼݺ‬ग़͠ͷҾ਺ɼ໭޲Λද‫͢ݱ‬ΔͨΊʹಋೖ͞ΕͨԾ૝ͷ੍‫ޚ‬ґଘઌ௖఺Ͱ͋

Γ஋Λ࢖༻͢ΔɽϑΟʔϧυ͓Αͼ഑ྻͰ͸ΦϒδΣ

ΔɽਤதͰ͸࣮ઢͷลͰσʔλґଘؔ܎Λɼ఺ઢͷลͰ੍ΫτΛ۠ผ͠ɼ഑ྻͰ͸ఴࣈͷҧ͍Λ۠ผ͢Δɽͭ·‫ޚ‬ґଘؔ܎Λࣔͨ͠ɽ͜Ε͸ՄಡੑͷͨΊͰɼ͜ͷ‫ޙ‬ͷ‫ܭ‬ΓɼಉҰΦϒδΣΫτͷಉҰϑΟʔϧυɼ͋Δ͍͸ಉࢉͰ͸ลͷछྨ͸۠ผ͠ͳ͍ɽ

Ұ഑ྻͷಉҰఴࣈʹΑͬͯಉҰϝϞϦྖҬʹΞΫηε
ͨ͠ͱ͖ɼϑΟʔϧυ͋Δ͍͸഑ྻʹΑΔಈతσʔλґଘؔ܎͕͋Δͱߟ͑Δɽ

c 2012 Information Processing Society of Japan

3.3 ಈతґଘؔ܎ʹΑΔ 3-gram ू߹ͷநग़ಈతґଘάϥϑ͔ΒɼลͰ઀ଓ͞Εͨ௖఺ 3 ͭͷฒͼΛ

4৘ใॲཧֶձ‫ڀݚ‬ใࠂ
IPSJ SIG Technical Reportྻ‫ޙͨ͠ڍ‬ɼϒϩοΫ p ͷ࣮ߦճ਺Λແࢹͯ͠ɼ͢ͳΘͪ• for จͳͲʹΑΔϧʔϓ࣮ߦʹ͍ͭͯɼ࣮ߦճ਺Λ 0pi Λ p ʹม‫ͯ͠׵‬ɼ3-gram ͷྻ‫ڍ‬Λߦ͏ɽ௚લʹґଘؔճ͔ɼ1 ճ͔ɼ2 ճҎ্͔ͱ͍͏ 3 छྨʹ෼ྨͨ͠ͱ

܎͕ͳ͍ઌ಄ͷลʹ͍ͭͯ͸ɼ௖఺͕ͳ͍͜ͱΛࣔ͢‫߸ه‬͖ɼϧʔϓ͝ͱͷ෼ྨ͕౳͍͠ɽ͜Ε͸ɼϧʔϓͷ࣮e Λ༻͍ͯྻ‫ڍ‬Λߦ͏ɽͨͱ͑͹ਤ 3 ͷάϥϑ͔Βґଘؔߦ‫ܧ‬ଓΛ൑ఆ͢Δ৚݅෼‫ ྩ໋ذ‬p ʹରͯ͠ p → p → p܎Λநग़͢Δ৔߹ɼe → 11 → 21 ɼ11 → 21 → 51 ͱ͍͏ͱ͍͏‫Ͱܗ‬ಈత੍‫ޚ‬ґଘؔ܎͕ൃੜ͠ɼ3-gram ʹ൓Α͏ʹಈతґଘάϥϑ্ͷ 3-gram Λநग़ͨ͠‫ޙ‬ɼͦΕΛө͞ΕΔͨΊͰ͋Δɽ

e → 1 → 2ɼ1 → 2 → 5 ͱ͍͏Α͏ʹ࣮ߦճ਺ͷ৘ใΛऔ͜ͷൺֱ͸࣮ߦύεʢ࣮ߦ͞Ε໋ͨྩͷྻʣ͕౳͍͜͠ͱ

Γআ͍ͨ΋ͷʹม‫͢׵‬Δɽ͜ΕʹΑΓɼfor จͷ 1 ճ໨ͷ͸อূͤͣɼ໋ྩͷ࣮ߦճ਺͕ҟͳ͍ͬͯͯ΋ɼಉ͡ґଘ৚݅൑ఆͱ 2 ճ໨ͷ৚݅൑ఆʢ51 , 52 ʣ͸ɼ͍ͣΕ΋ೖྗؔ܎͕ੜ͍ͯ͡Δ‫ݶ‬Γ͸ಉҰͱ൑ఆ͢Δɽͨͱ͑͹ਤ 1 ͷ͞Εͨ஋ N Λ࢖༻͢Δ͕ɼͦΕʹؔ͢Δ‫ܦ‬࿏͸ 1 → 2 → 5ϓϩάϥϜͷ৔߹ɼN=0, 1, 2, 3 ·Ͱ͸ 71 → 72 → 73 ͷͱ͍͏ಉҰͷ 3-gram ʹͳΔɽΑ͏ʹϧʔϓ಺෦ͷσʔλґଘؔ܎͕ 3-gram ʹ൓ө͞ΕΔͨΊ۠ผՄೳͰ͋Δ͕ɼͦΕҎ্͸ 3-gram ͷ௕͞Ͱ͸

3.4 3-gram ू߹ͷൺֱද‫͍ͨͳ͖Ͱݱ‬Ίɼ‫ػ‬ೳͷ࣮ߦճ਺͕ͦΕҎ্૿͑ͯ΋2 ͭͷ࣮ߦτϨʔε͔ΒͦΕͧΕऔಘͨ͠ 3-gram ू߹

3-gram ͷू߹͸มԽͤͣɼ۠ผ͢Δ͜ͱ͕Ͱ͖ͳ͍ɽͦͷΛൺֱ͠ɼͦͷ‫ڞ‬௨ू߹ɼࠩू߹Λநग़͢Δɽͨͱ͑͹ɼ͔ΘΓɼϧʔϓͷ࣮ߦճ਺ʹΑΒͣɼ‫ࢉܭ‬ͷࠩҟ΍৚݅෼

ਤ 3 ͷάϥϑͱਤ 4 ͷάϥϑ͔ΒಘΒΕͨ 3-gram Λൺֱ‫ذ‬ͷࠩҟ͕ੜ͔ͨ͡Ͳ͏͔͚ͩʹ஫໨͢Δ͜ͱ͕Ͱ͖Δɽ

ͨ͠৔߹ɼม਺ sum ʹؔ͢Δ 3-gram 4 → 6 → 9 ͕ਤ 3 ʹ‫ݻ‬༗Ͱ͋ΓɼҰํͰ 4 → 6 → 6ɼ6 → 6 → 9ɼͱ͍͏ 2 ͭ
ͷ 3-gram ͸ਤ 4 ʹ‫ݻ‬༗Ͱ͋Δɽ

4. έʔεελσΟఏҊख๏ͷ༗ޮੑΛ‫͢ূݕ‬ΔͨΊʹɼಉҰϓϩάϥϜ

࠷ऴతͳ݁Ռ͸ɼ໋ྩϒϩοΫʹׂΓ౰ͯͨ ID ͷ 3-ͷҟͳΔೖྗʹର͢Δ࣮ߦτϨʔεΛఏҊख๏ʹΑͬͯ

gram ͱͳ͍ͬͯΔ͕ɼόΠτίʔυʹ‫ه‬࿥͞Ε͍ͯΔ໋ྩ

ൺֱ͠ɼϓϩάϥϜಈ࡞ཧղͷέʔεελσΟΛߦͬͨɽͱߦ൪߸ͷରԠදʹ‫͍ͯͮج‬ɼ໋ྩϒϩοΫ͔Β‫ͬͳʹݩ‬έʔεελσΟͷର৅͸ɼDaCapo ϕϯνϚʔΫ [5] ʹऩͨιʔείʔυͷϑΝΠϧ໊ͱߦ൪߸΁ͱม‫ͯ͠׵‬Ӿཡ͢࿥͞Εͨ 2 ͭͷ Java ΞϓϦέʔγϣϯ batik, fop Ͱ͋ΔɽΔ͜ͱ΋ՄೳͰ͋Δɽͨͱ͑͹ 4 → 6 → 9 ͱ͍͏ϒϩο

DaCapo ϕϯνϚʔΫ͸ɼΞϓϦέʔγϣϯ͝ͱʹɼsmallɼΫؒͷ 3-gram ͸ɼਤ 1 ͷιʔείʔυʹରԠ෇͚ΔͱҎ

defaultɼlarge ͱ͍͏ 3 ͭͷ࣮ߦΦϓγϣϯΛఏ‫͍ͯ͠ڙ‬Լͷ 3 ߦʹରԠ͢Δɽ

ΔɽͦΕͧΕ͕࣮ߦ͢Δ‫ػ‬ೳʹ͍ͭͯ໌֬ͳ৘ใ͕༩͑Β

2: int sum = 0;Ε͍ͯΔΘ͚Ͱ͸ͳ͍͕ɼsmall ΑΓ͸ default ͕ɼdefault

4: sum = sum + i;

ΑΓ͸ large ͷ΄͏͕ଟ͘ͷ‫ػ‬ೳΛ࣮ߦ͠ɼඪ४ग़ྗʹϝο

6: System.out.println(sum);ηʔδΛग़ྗ͢Δɽbatik, fop ʹ͍ͭͯɼέʔεελσΟ͜ͷΑ͏ͳࠩҟͷҰཡΛఏࣔ͢Δ͜ͱʹΑΓɼ։ൃऀ͸࣮։࢝࣌఺Ͱ֤ΞϓϦέʔγϣϯʹର͍ͯ࣋ͬͯͨ͠զʑͷߦτϨʔεͷࠩҟΛ෼ੳ͢Δ͜ͱ͕Ͱ͖Δɽ

ࣄલ஌ࣝ͸ҎԼͷ௨ΓͰ͋ΔɽఏҊख๏ʹ͓͍ͯɼ2 ͭͷ࣮ߦτϨʔε͔ΒಘΒΕͨ

batik

3-gram ू߹͕౳͍͠৔߹ɼͦΕΒͷ࣮ߦτϨʔε͔ΒಘApache Batik ͸ɼScalable Vector Graphics ը૾ΛऔΒΕΔςετΧόϨοδʹؔͯ͠ҎԼͷੑ࣭͕੒ΓཱͭɽΓѻ͏ιϑτ΢ΣΞͰ͋ΔɽDaCapo ϕϯνϚʔΫʹ• ϒϥϯνΧόϨοδ͕౳͍͠ɽ2 ͭͷ࣮ߦτϨʔεͰ͓͚Δ batik ͷ࣮ߦ͸ɼ֦ுࢠ svg ͷը૾ϑΝΠϧΛ

࣮ߦ͞Εͨ৚݅෼‫ذ‬ͷू߹͕ɼͦͷ··ಈత੍‫ޚ‬ґଘೖྗͱͯ͠ɼͦΕΛ֦ுࢠ png ͷը૾ϑΝΠϧʹม‫׵‬ลͷू߹ͱͯ͠ 3-gram ͷू߹ʹ‫·ؚ‬ΕΔͨΊɼϒϥ͢Δ‫ػ‬ೳΛ࣮ߦ͢Δ. ࣮ߦΦϓγϣϯͱͯ͠ small ͕ϯνΧόϨοδ͕ҟͳΔͳΒඞͣ 3-gram ͷू߹ʹ΋બ͹Εͨ৔߹͸ɼ୯ҰͷϑΝΠϧ mapWaadt.svg ͷมมԽ͕ੜ͡Δɽͳ͓ɼϒϥϯνΧόϨοδ͕౳ͯ͘͠

‫׵‬Λߦ͍ɼdefault ͕બ͹Εͨ৔߹͸ɼmapWaadt.svgɼ

΋ɼ৚݅෼‫࢖ʹذ‬ΘΕΔσʔλͷґଘ‫͕ݩ‬ҟͳΔ৔߹

mapSpain.svgɼsydney.svg ͱ͍͏ 3 ͭͷϑΝΠϧͷม͸ɼ3-gram ͷू߹ͱͯ͠͸ҟͳΔ΋ͷͱͳΔ৔߹͕‫׵‬Λߦ͏͜ͱ͕ඪ४ग़ྗʹॻ͖ग़͞ΕΔɽ

͋Δɽ

fop

• def-use ΧόϨοδ͕౳͍͠ɽdef-use ؔ܎͸ಈతσʔApache FOP ͸ XSL formatting objects (XSL-FO)λґଘลͷఆٛʹରԠ͢ΔͨΊɼdef-use ΧόϨοδ

ͱ‫ݺ‬͹ΕΔೖྗϑΝΠϧΛղੳ͠ɼը૾΍ςΩετͳ͕ҟͳΔͳΒɼͦΕʹରԠ͢Δ 3-gram ͷ͕ࠩ‫ݕ‬ग़ͰͲ༷ʑͳ‫ͦͰࣜܗ‬ͷ಺༰ΛՄࢹԽ͢ΔϨϯμϦϯά

͖Δɽdef-use ΧόϨοδ͕౳ͯ͘͠΋ɼσʔλґଘιϑτ΢ΣΞͰ͋ΔɽDaCapo ϕϯνϚʔΫʹ͓͚Δลͷ‫ܦ‬࿏ͳͲ͕ҟͳΔ৔߹ɼ3-gram ͱͯ͠͸ҟͳΔ

fop ͷ࣮ߦ͸ɼpdf ϑΝΠϧΛ࡞੒͢Δɽඪ४ग़ྗʹ΋ͷʹͳΔՄೳੑ͕͋Δɽ͸Կ΋ϝοηʔδΛग़ྗ͠ͳ͍ͨΊɼsmall ͱ default

c 2012 Information Processing Society of Japan

5৘ใॲཧֶձ‫ڀݚ‬ใࠂ
IPSJ SIG Technical Reportද 2 ֤࣮ߦτϨʔεʹ‫ݻ‬༗ɾ‫ڞ‬௨ͷ 3-gram ͷ‫਺ݸ‬࣮ߦτϨʔε໊‫ݻ‬༗batik small

405

batik default

7,897

fop small

1,256

fop default

4,959

‫ڞ‬௨

14,413
10,676

Ͱඪ४ग़ྗ͔Β໌֬ͳಈ࡞ͷҧ͍Λೝࣝ͢Δ͜ͱ͸Ͱ͖ͳ͍ɽϓϩάϥϜͷ࣮ߦΛ‫ه‬࿥͠ɼJava ͷόΠτίʔυ໋ྩͷ࣮ߦॱংɼJava Ծ૝ϚγϯͷϩʔΧϧม਺ͷঢ়ଶ΍ΦϖϥϯυελοΫͷঢ়ଶɼώʔϓϝϞϦͷঢ়ଶͳͲΛ࠶‫ݱ‬Ͱ͖Δ࣮ߦτϨʔεΛ‫ه‬࿥ͨ͠ɽͦͯ͠ɼsmall ͱ default[SVGConverter.java]
public void setDst(File dst) {492:
this.dst = dst;}
public void execute() throws
SVGConverterException {677:
List sources = computeSources();
List destFiles = null;679:
if (sources.size() == 1 &&dst != null && isFile(dst)) {dstFiles = new ArrayList();dstFiles.add(dst);}
else {
684:
dstFiles = computeDstFiles(sources);}ͱ͍͏ 2 ͭͷ࣮ߦτϨʔεΛͦΕͧΕఏҊख๏ʹΑͬͯ

3-gram ͷू߹΁ͱม‫ͨ͠׵‬ɽද 1 ʹɼέʔεελσΟͷ

ਤ 5 batik small ͱ default Ͱ‫ݕ‬ग़͞Εͨಈ࡞ͷࠩҟର৅ͱ֤࣮ͨ͠ߦτϨʔεͷຊདྷͷ࣮ߦ࣌ؒͱɼͦͷ࣮ߦಈ࡞Λ͢΂ͯ‫ه‬࿥࣮ͨ͠ߦτϨʔεͷϑΝΠϧͷ૯༰ྔɼ͔ͦ͜Βநग़͞ΕΔ 3-gram ͷू߹ͷϑΝΠϧ༰ྔɼͦ͠
ͯ 3-gram ू߹ͷཁૉ਺Λࣔ͢ɽද 1 ͔ΒɼϑΝΠϧʹอΕɼͦΕ͕ʮม‫ݩ׵‬ϑΝΠϧ͕ 1 ͭͰ͸ͳ͍ʯͱ൑ఆ͞Ε

ଘ͢Δͱ GB ୯Ґͷ৘ใΛ‫ؚ‬Ή‫ڊ‬େͳ࣮ߦτϨʔεʹରͯ͠ else અͷจͷ࣮ߦʹͭͳ͕ͬͨͱಡΈऔΕΔɽsmallͯ΋ɼಈతґଘάϥϑΛ 3-gram ͷू߹ͱͯ͠ද‫͢ݱ‬Δ͜

ͷ࣮ߦτϨʔεʹ͸ 492 → 679 → 684 ͱ͍͏ 3-gram ͕ͱΑͬͯɼ࣮ߦτϨʔεͷಈ࡞Λඇৗʹগͳ͍ཁૉ਺Ͱද

ଘࡏ͓ͯ͠Γɼ࣮ߦτϨʔεΛ֬ೝͨ͠ͱ͜Ζɼͪ͜Β͸‫͕ͱ͖ͨ͜Ͱݱ‬Θ͔Δɽྫ͑͹ɼbatik ͷ default ͷ࣮ߦม‫׵‬ର৅ͷϑΝΠϧ͕ͨͩ 1 ͭͳͷͰग़ྗର৅͕ϑΝΠϧτϨʔεͷ৔߹ɼ3,131 ‫ݸ‬ͷϝιου͕ͷ΂ 1700 ສճ΄Ͳ͔Ͳ͏͔Λ൑ఆ͢Δ 3 ͭ໨ͷ৚݅จ·ͰਐΈɼͦͷ‫ ޙ‬else࣮ߦ͞ΕΔ͕ɼͦͷಈ࡞Λ 3-gram ू߹Ͱද͢ͱ 470KB ఔ

ʹਐΜͰ͍ͨɽ͜ͷॲཧͷҧ͍͸ɼbatik ͸୯ҰϑΝΠϧ౓ͷϑΝΠϧͱͯ͠อଘ͢Δ͜ͱ͕ՄೳͰ͋ͬͨɽ·ͨɼΛม‫͢׵‬Δͱ͖͸ग़ྗઌͱͯ͠ϑΝΠϧ໊ͱσΟϨΫτϦ

batik, fop ͷ྆ํͰɼ࣮ߦτϨʔεͷαΠζͷࠩʹൺ΂ͯɼ໊ͷ޷͖ͳํΛར༻Ͱ͖Δ͕ɼෳ਺ϑΝΠϧΛม‫͢׵‬Δͱ

3-gram ू߹ͷཁૉ਺ͷ૿Ճྔ͸‫ݶ‬ΒΕ͍ͯΔɽ͜Ε͸ɼ͖ͷग़ྗઌͷࢦఆ͸ඞͣσΟϨΫτϦͱͳΔɼͱ͍͏‫ػ‬ೳbatik ͷ৔߹͸ϑΝΠϧͷม‫͕਺ݸ׵‬ҟͳΔͱ͍ͬͨΑ͏ͷ࣮૷͕Ө‫ͨ͠ڹ‬΋ͷͩͱߟ͑ΒΕΔɽ

ʹɼϕϯνϚʔΫͷ࣮ߦτϨʔε͕ಉ͡छྨͷ‫ػ‬ೳͷ࣮ߦ

ਤ 5 ͷ 684 ߦ໨ʹॻ͔Εͨ computeDstFiles ͱ͍͏ϝ‫ن‬໛Λมߋ͢Δͱ͍͏‫Ͱܗ‬ઃ‫͞ܭ‬Ε͍ͯΔͨΊͩͱߟ͑Βιουͷ‫ͼݺ‬ग़͠ઌͰ͸ɼsources ʹ֨ೲ͞ΕͨϑΝΠϧΕΔɽΛॱʹॲཧ͍ͯ͠ΔͷͰɼϧʔϓͷ࣮ߦճ਺͕ 3-gram ͷࠩͱͯ͠‫ݕ‬ग़͞Ε͕ͨɼͦΕҎ֎ͷґଘؔ܎͸ small ͱ

4.1 ࣮ߦτϨʔεͷൺֱ݁Ռද 2 ʹ͸ɼ3-gram ू߹Λൺֱ͠ɼ֤࣮ߦτϨʔεʹ‫ݻ‬batik Ͱ౳͍͜͠ͱ͔ΒɼϑΝΠϧ͝ͱͷॲཧʹ͸ಛʹมԽ͕ͳ͍ͱਪଌͰ͖ͨɽ

༗ͷ 3-gram ͱɼ2 ͭͷ࣮ߦτϨʔεʹ‫ڞ‬௨ͷ 3-gram ʹ͜ͷΑ͏ʹɼsmall ͱ default Ͱ͸ॲཧͷ࣮ߦճ਺ʹࠩ෼ྨͨ݁͠ՌΛࣔ͢ɽ͔͜͜Βɼ֤ΞϓϦέʔγϣϯͷ࣮͕͋ͬͯ΋ɼͦͷ͕ࠩӨ‫ͨ͠ڹ‬ൣғ͚ͩʹ஫໨ͯ͠ௐࠪΛߦτϨʔε͕ґଘؔ܎ͷଟ͘Λ‫ڞ‬༗͓ͯ͠Γɼsmall Ͱ࣮ߦ͑ΔΑ͏ʹͳΔ఺͕ɼఏҊख๏ͷಛ௃Ͱ͋Δͱ͍͑Δɽߦ͞Εͨ‫ػ‬ೳͷଟ͕͘ default ʹ΋‫·ؚ‬Ε͍ͯΔ͜ͱ͕ಡͳ͓ɼbatik default ‫ݻ‬༗ͷ 3-gram ʹ͸ɼsmall Ͱ͸࣮ߦΈऔΕΔɽ͞Ε͍ͯͳ͍ଟ਺ͷΫϥεɼϝιου͕‫·ؚ‬Ε͍ͯͨ͜ͱ

ಘΒΕͨ 3-gram ͷू߹ͷ͔ࠩΒ batik small ͱ default͔Βɼdefault ͸ small ͱಉ͡ಈ࡞Λ 3 ճ‫܁‬Γฦ͚ͩ͢Ͱ

ͷಈ࡞ͷҧ͍͕ಡΈऔΕͨ৘ใͷྫͱͯ͠ɼιʔείʔυ͸ͳ͘ɼ͞Βʹ௥ՃͷॲཧΛ࣮ߦ͍ͯ͠Δͱ൑அ͢Δ͜ͱͷൈਮΛਤ 5 ʹࣔ͢ɽਤதͷߦ൪߸͸ɼ3-gram ʹؔ܎͕͢ՄೳͰ͋ͬͨɽҰํͰɼ৽͍͠ϝιου͕ 1 ࣮ͭߦ͞ΕΔ৔ॴʹͷΈ͍ࣔͯ͠Δɽbatik ͸ࢦఆ͞Εͨ SVG ϑΝ͚ͨͩͰ΋ɼͦͷϝιουʹؔ͢Δଟ਺ͷ 3-gram ͕ࠩ෼Πϧʹର͢Δม‫ॲ׵‬ཧΛ࣮ߦ͢Δ͕ɼdefault ͷ࣮ߦτϨʔͱͯ͠நग़͞ΕΔͱ͍͏ͷ͕ఏҊख๏ͷऑ఺Ͱ͋Δɽࠓ‫ޙ‬εʹ‫ݻ‬༗ͷ 3-gram ͱͯ͠ 677 → 679 → 684 ͱ͍͏‫ܦ‬࿏ఏҊख๏Λ‫͍ͨͯ͘͠༻׆‬Ίʹ͸ɼͦͷΑ͏ͳτϨʔε‫ݻ‬͕ଘࡏ͠ɼ677 ߦ໨Ͱ୅ೖ͞Εͨ sources ͕ 679 ߦ໨ͷ if

༗ͷ 3-gram ΛΫϥε΍ϝιου୯ҐͰ੔ཧͯ͠Ӿཡ͢Δ

จͷ৚݅અͷ 1 ͭ໨ͷ৚݅ sources.size()==1 Ͱ࢖༻ͨ͞ΊͷϏϡʔΞͷ੔උ͕ඞཁͰ͋Δͱߟ͑ΒΕΔɽ

c 2012 Information Processing Society of Japan

6৘ใॲཧֶձ‫ڀݚ‬ใࠂ
IPSJ SIG Technical Reportද 1 ֤࣮ߦτϨʔε͝ͱͷ࣮ߦ࣌ؒͱϑΝΠϧͷαΠζ
࣮ߦτϨʔεϑΝΠϧͷαΠζ
3-gram ϑΝΠϧͷαΠζ

࣮ߦτϨʔε໊࣮ߦ࣌ؒbatik small

2,542ms

7.39GB

304KB

14,818batik default

4,430ms

40.2GB

470KB

22,310fop small

1,747ms

1.53GB

253KB

11,932fop default

2,886ms

8.56GB

336KB

15,6351

3-gram ू߹ͷཁૉ਺

ΔൺֱͰ͸‫ݕ‬ग़͢Δ͜ͱ͕Ͱ͖ͳ͍Α͏ͳґଘؔ܎ͷ‫ܦ‬࿏

2͕࣮ߦτϨʔεʹ‫·ؚ‬Ε͍ͯΔ͔Ͳ͏͔Λௐࠪͨ͠ɽ

3-gram Ͱ͸ද‫͞ݱ‬ΕΔ͕ 2-gram ʹΑΔද‫͍ͳ͖Ͱ͕ݱ‬3‫ܦ‬࿏ͷߏ଄Λਤ 6 ʹࣔ͢ɽ2-gram Ͱ͸ 4 ຊͷลͷू߹ͱ
4

ਤ 6
ද 3

ͯ͠༩͑ΒΕΔͨΊɼͨͱ͑͹ 1 → 3 → 4ɼ2 → 3 → 5 ͱ

52-gram ͱ 3-gram Ͱ͕ࠩੜ͡Δಈతґଘؔ܎ͷྫ

3-gram Λ࢖Θͳ͍ͱґଘؔ܎ͷ‫ܦ‬࿏͕ೝࣝͰ͖ͳ͔ͬͨϒϩοΫͷ਺࣮ߦτϨʔε໊͍͏ 2 ͭͷ‫ܦ‬࿏͕‫ʹط‬ଘࡏ͢Δͱ͖͸ɼ৽ͨʹ 2 → 3 → 4
ͱ͍͏ 3-gram ͕ग़‫ͯ͠ͱͨ͠ݱ‬΋ɼ2-gram ͷू߹Ͱ͸
ೝࣝ͢Δ͜ͱ͕Ͱ͖ͳ͍ɽ͜Ε͸ɼ͋ΔϒϩοΫ B ʢਤ 6தͰͷ௖఺ 3ʣ͔Β‫ͯݟ‬ɼͦ͜ʹґଘลΛ΋ͭϒϩοΫ໋͕ྩϒϩοΫ਺batik small

191

batik default296

fop small161

fop default

171

x ‫ݸ‬ɼB ͔Βͷґଘล͕͋ΔϒϩοΫ͕ y ‫͋ݸ‬Δͱ͢Δ
ͱɼ࣮ߦ‫ܦ‬࿏ͱͳΔ 3-gram ͕࠷େͰ xy ‫ݸ‬ଘࡏ͢Δͷʹ
ର͠ɼ2-gram Ͱ͸ྡ઀ͨ͠ϒϩοΫؒͷ x + y ௨Γͷؔ
܎·Ͱ͔͠औΓѻ͑ͳ͍ͨΊͰ͋Δɽ͜ͷΑ͏ͳ 3-gramू߹Ͱͳ͚Ε͹ଘࡏΛೝࣝͰ͖ͳ͍Α͏ͳ࣮ߦ‫ܦ‬࿏Λ࣋ͭ

[SVGSVGElementBridge.java]
public GraphicsNode createGraphicsNode(...) {CanvasGraphicsNode cgn;
cgn = (CanvasGraphicsNode)instantiateGraphicsNode();160:
cgn.setViewingTransform(viewingTransform);[SVGAbstractTranscoder.java]
protected void transcode(Document document, ...) {CanvasGraphicsNode cgn =getCanvasGraphicsNode(gvtRoot);287:
cgn.setViewingTransform(Px);໋ྩϒϩοΫͷ਺Λ֤࣮ߦτϨʔε͔Β‫ݕ‬ग़ͨ͠ͱ͜Ζɼ
ද 3 ͷΑ͏ͳ݁Ռ͕ಘΒΕͨɽ͜͜Ͱͷ‫਺ݸ‬͸ɼਤ 6 ʹ͓͚ΔϒϩοΫ 3 ʹ૬౰͢Δ໋ྩϒϩοΫͷ਺Ͱ͋Δɽ͜ͷ݁Ռ͔Βɼ3-gram ͷར༻͕ɼ2-gram ΑΓ΋࣮ߦτϨʔεͷΑΓਖ਼֬ͳද‫ͯ͠ͱݱ‬ҙຯ͕͋Δ͜ͱ͕֬ೝͰ͖Δɽ·ͨɼbatik ͷൺֱͰ͸ 20 ‫ݸ‬ɼfop Ͱ͸ 14 ‫ݸ‬ͷ 3-gram ͕ɼ

2-gram Λ࢖ͬͯͷൺֱͰ͸‫ݟ‬ಀ͞ΕΔ͜ͱΛ֬ೝͨ͠ɽ
࣮ࡍͷྫͱͯ͠͸ɼ࣍ͷΑ͏ͳ 3-gram ͷ૊͕‫͛ڍ‬ΒΕΔɽ

SVGSVGElementBridge.java:160-> CanvasGraphicsNode.java:115[CanvasGraphicsNode.java]
public void setViewingTransform(
AffineTransform at) {115:
this.viewingTransform = at;116:
if (positionTransform != null) {117:
transform = new AffineTransform(
positionTransform);
118:
if (viewingTransform != null)
119:transform.concatenate(viewingTransform);120:} else if (viewingTransform != null)
121:
transform = new AffineTransform(
viewingTransform);ਤ 7 2-gram Ͱ͸ද‫ܦ͍ͳ͖Ͱݱ‬࿏ʹରԠ͢Δ batik ͷιʔείʔυʢൈਮʣ

4.2 3-gram ͱ 2-gram ͷൺֱຊ‫Ͱڀݚ‬͸ 3-gram ͷू߹Λൺֱର৅ʹ࢖༻͕ͨ͠ɼ

2-gramɼͭ·Γಈతґଘลͷू߹Λ୯७ʹൺֱ͢Δ͚ͩͰ΋ɼϒϥϯνΧόϨοδ΍ def-use ΧόϨοδ͕౳͍͜͠

-> CanvasGraphicsNode.java:119
SVGAbstractTranscoder.java:287-> CanvasGraphicsNode.java:115-> CanvasGraphicsNode.java:121͜ͷ 2 ͭͷ 3-gram ʹରԠ͢ΔιʔεϑΝΠϧ 3 ͭͷஅย
Λਤ 7 ʹࣔ͢ɽਤதͰ͸ɼґଘؔ܎ʹؔΘΔίʔυҎ֎͸লུͨ͠ɽ͜ΕΒͷ 3-gram ͸ɼ͍ͣΕ΋ઌ಄ͷཁૉ͕ϝιου‫ͼݺ‬ग़͠‫͓ͯͬͳͱݩ‬ΓɼsetViewingTransformϝιουͷ಺෦ͰΦϒδΣΫτͷঢ়ଶͷࠩʹΑΓ৚݅෼‫ذ‬͕‫͖݁ͨى‬ՌΛද‫͍ͯ͠ݱ‬Δɽ2-gram Ͱ͸ɼ2 ͭͷ‫ͼݺ‬ग़͠‫ݩ‬ͷͲͪΒ͔Βͷσʔλϑϩʔ͕ if จͷͲͪΒͷ‫ܦ‬࿏ʹͨͲΓண͍͔ͨද‫͞ݱ‬Εͳ͍͕ɼ3-gram Λ༻͍Δͱґଘؔ܎ͷ‫ܦ‬࿏Λ஌Δ͜ͱ͕༰қͰ͋ΔɽN-gram ͷ N Λେ͖͍ͯ͘͘͠ͱ͞Βʹ‫ܦ‬࿏ͷࣝผೳྗ͕޲্͢Δ͜ͱ͸‫ظ‬଴͞ΕΔ͕ɼͦͷίετͱޮՌͷτϨʔυΦϑͷධՁ͸ࠓ‫ޙ‬ͷ՝୊Ͱ͋ΔɽͱΛ֬ೝ͢Δ͜ͱ͕Ͱ͖Δɽͦ͜Ͱɼ2-gram ͷू߹ʹΑc 2012 Information Processing Society of Japan

7৘ใॲཧֶձ‫ڀݚ‬ใࠂ
IPSJ SIG Technical Report

5. ·ͱΊ

[5]ຊ‫Ͱڀݚ‬͸ɼJava ϓϩάϥϜͷ 2 ͭͷ࣮ߦτϨʔεΛൺֱ͠ɼ‫ڞ‬௨͢Δґଘؔ܎ͱ֤τϨʔεʹ‫ݻ‬༗ͷґଘؔ܎Λ‫ٻ‬ΊΔख๏ΛఏҊͨ͠ɽఏҊख๏Ͱ͸ɼಈతґଘάϥϑશମΛൺֱ͢Δ͔ΘΓʹɼಈతґଘάϥϑΛ໋ྩͷϒϩοΫ
୯ҐΛ௖఺ͱͨ͠ 3-gram ͷू߹ʹม‫ͯ͠׵‬ൺֱΛߦͬͯ
͍Δɽಈతґଘάϥϑͷลʢ2-gramʣͷू߹ͰϒϥϯνΧ
όϨοδ΍ def-use ΧόϨοδͳͲͷಉҰੑΛอূͰ͖Δ[6]

͕ɼ3-gram ͸͞Βʹৄࡉͳൺֱͱͳ͍ͬͯΔɽఏҊख๏ͷ༗ޮੑΛ‫͢ূݕ‬ΔͨΊʹɼϓϩάϥϜಈ࡞ཧղͷέʔεελσΟΛߦͬͨɽDaCapo ϕϯνϚʔΫʹऩ[7]࿥͞Εͨ 2 ͭͷ Java ΞϓϦέʔγϣϯ batik, fop ͷ࣮ߦτϨʔεʹରͯ͠ఏҊख๏Λద༻͠ɼಘΒΕͨࠩ෼ͷࣄྫ

[8]Λ֬ೝͨ͠ɽͦͷ݁Ռɼ࣮ߦτϨʔεͷ 3-gram ू߹͸࣮ߦτϨʔεʹൺ΂ͯඇৗʹখ͞ͳσʔλྔͰද‫͢ݱ‬Δ͜ͱ
͕Ͱ͖Δ͜ͱɼಉҰͷॲཧ͕ෳ਺ճ࣮ߦ͞Ε͍ͯΔΑ͏ͳ৔߹ͷࠩҟΛແࢹͰ͖Δ͜ͱΛ֬ೝ͠ɼ·ͨɼ3-gram ʹ[9]ΑΔൺֱ͕༗ޮʹಇ͘ͱࢥΘΕΔࣄྫ΋਺ଟ࣮͘ߦτϨʔεʹ‫·ؚ‬Ε͍ͯͨ͜ͱΛ֬ೝͨ͠ɽ

[10]

3-gram ͸খ͞ͳࠩҟΛநग़Ͱ͖Δ͕ɼ͋Δϝιου͕Ұํͷ࣮ߦτϨʔεͰ͸࣮ߦ͞ΕΔ͕ଞํͰ͸࣮ߦ͞Εͳ͍ͱ͍͏৔߹ɼͦͷϝιουʹؔ͢Δಈతґଘؔ܎͔Βଟ

[11]

਺ͷ 3-gram ͕ࠩ෼ͱͯ͠நग़͞Εͯ͠·͏ɽͦͷͨΊɼΫϥε΍ϝιου୯ҐͰ 3-gram ͷࠩ෼Λ੔ཧͯ͠ӾཡͰ
͖ΔΑ͏ͳϏϡʔΞΛ੔උ͠ɼ։ൃऀ͕࣮ߦτϨʔεΛ෼[12]ੳ͢Δ࡞‫ʹۀ‬ద༻͢Δ͜ͱ͕ࠓ‫ޙ‬ͷ՝୊Ͱ͋Δɽ·ͨɼຊ‫Ͱڀݚ‬͸ 3-gram Λద༻͢Δ͜ͱͰϧʔϓͷճ਺Λ 0 ճɼ

1 ճɼෳ਺ճͱΛ۠ผ͢Δ͜ͱ΍ɼσʔλґଘؔ܎ͷ୹͍‫ܦ‬࿏Λ۠ผ͢Δ͜ͱΛՄೳͱ͕ͨ͠ɼҰൠʹ N-gram ͷ NΛେ͖͘͢Δͱ͞Βʹ‫ܦ‬࿏ͷࣝผೳྗ͕େ͖͘ͳΔ͜ͱ͕

[13]‫ظ‬଴Ͱ͖Δ͜ͱ͔ΒɼͦͷίετͱޮՌͷτϨʔυΦϑͷධՁ΋·ͨࠓ‫ޙ‬ͷ՝୊Ͱ͋Δɽँࣙຊ‫ڀݚ‬͸Պ‫ݚ‬අ No.26280021 ͷॿ੒Λಘͨɽ[14]ࢀߟจ‫ݙ‬
[1]

[2]

[3]

[4]

Zaidman, A.: Scalability solutions for program comprehension through dynamic analysis, PhD Thesis, University of Antwerp (2006).
Johnson, N. M., Caballero, J., Chen, K. Z., McCamant,
S., Poosankam, P., Reynaud, D. and Song, D.: Diﬀerential slicing: Identifying causal execution diﬀerences forsecurity applications, Proceedings of the IEEE Symposium on Security and Privacy, pp. 347–362 (2011).
Abramson, D., Chu, C., Kurniawan, D. and Searle, A.:
Relative debugging in an integrated development environment, Software Practice and Experience, Vol. 39,
No. 14, pp. 1157–1183 (2009).
Agrawal, H. and Horgan, J. R.: Dynamic program slicing, Proceedings of the ACM SIGPLAN conference on
Programming Language Design and Implementation,c 2012 Information Processing Society of Japan


[15]

[16]

pp. 246–256 (1990).
Blackburn, S. M., Garner, R., Hoﬀman, C., Khan, A. M.,
McKinley, K. S., Bentzur, R., Diwan, A., Feinberg,D., Frampton, D., Guyer, S. Z., Hirzel, M., Hosking,A., Jump, M., Lee, H., Moss, J. E. B., Phansalkar,
A., Stefanović, D., VanDrunen, T., von Dincklage,
D. and Wiedermann, B.: The DaCapo Benchmarks:
Java Benchmarking Development and Analysis, Proceedings of the 21st annual ACM SIGPLAN conference on Object-Oriented Programing, Systems, Languages, and Applications, pp. 169–190 (online), DOI:
http://doi.acm.org/10.1145/1167473.1167488 (2006).
Zeller, A.: Why Programs Fail - A Guide to Systematic Debugging, the Second Edition, Morgan Kaufmann(2011).
Lewis, B.: Debugging Backwards in Time, Proceedings of the 5th International Workshop on
Automated Debugging, (online), available fromhttp://arxiv.org/html/cs/0309027v4 (2003).
Ko, A. and Myers, B.: Debugging Reinvented: Asking and Answering Why and Why Not Questions about
Program Behavior, Proceedings of the 30th International Conference on Software Engineering, pp. 301–310(2008).
Eisenbarth, T., Koschke, R. and Simon, D.: Locating
features in source code, IEEE Transactions on Software
Engineering, Vol. 29, No. 3, pp. 210–224 (2003).
Cornelissen, B. and Moonen, L.: Visualizing similarities
in execution traces, Proceedings of the 3rd Workshop
on Program Comprehension through Dynamic Analysis(PCODA), pp. 6–10 (2007).
Trumper, J., Dollner, J. and Telea, A.: Multiscale visualcomparison of execution traces, Proceedings of the 21stIEEE International Conference on Program Comprehension, pp. 53–62 (2013).
Miranskyy, A. V., Madhavji, N. H., Gittens, M. S., Davison, M., Wilding, M. and Godwin, D.: An iterative,
multi-level, and scalable approach to comparing execution traces, Proceedings of the the 6th joint meetingof the European Software Engineering Conference andthe ACM SIGSOFT symposium on the Foundations ofSoftware Engineering, pp. 537–540 (2007).
Zhu, H., Hall, P. a. V. and May, J. H. R.: Software unit test coverage and adequacy, ACM Computing Surveys, Vol. 29, No. 4, pp. 366–427 (online), DOI:
10.1145/267580.267590 (1997).
Zhang, X., Tallam, S. and Gupta, R.: Dynamic slicing long running programs through execution fast forwarding, Proceedings of the 14th ACM SIGSOFT International Symposium on Foundations of Software Engineering, pp. 81–91 (2006).
Matsumura, T., Ishio, T., Kashima, Y. and Inoue, K.:
Repeatedly-Executed-Method Viewer for EﬃcientVisualization of Execution Paths and States in Java, Proceedings of the 22nd International Conference on Program
Comprehension (2014).
Xin, B. and Zhang, X.: Eﬃcient Online Detection of
Dynamic Control Dependence, Proceedings of the ACM
SIGSOFT International Symposium on Software Testing and Analysis, pp. 185–195 (2007).

8