《半構造化テキストに対する文字列照合アルゴリズム.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、半構造化テキストに対する文字列照合アルゴリズム喜田拓也*貴福友晴†竹田正幸†*九州大学附属図書館研究開発室†九州大学システム情報科学府情報理学専攻発表者：　喜田拓也発表内容研究の目的既存の手法我々のアプローチ文字列照合による処理の利点と問題点提案アルゴリズム誤検出を回避する方法パスを考慮した照合処理実験結果まとめ22001年度冬のLAシンポジウム既存の手法XML文書XML文書メモリプログラムDOMAPIperson“”person/name“”person/name/firstMakikoperson/

2、name/lastTanaka……personnamefirstlastMakikoTanakaＸＭＬパーサー32001年度冬のLAシンポジウム我々のアプローチXML文書XML文書メモリプログラム文字列照合アルゴリズムMakikoTanaka42001年度冬のLAシンポジウム利点巨大なXML文書や大量の文書群を一括に処理複数の質問を同時に処理木構造処理が高速少ないメモリで可様々な応用XML文書52

3、001年度冬のLAシンポジウム文字列照合問題Patternmatchingisoneofthemostfundamentaloperationsinstringprocessing.Recently,anewtrendforacceleratingpatternmatchinghasemerged:Speedinguppatternmatchingbytextcompression.Fromthetraditionalcriteriafordatacompression,i.e.,compressionrati

4、oandcompression/decompressiontime,adaptivedictionarymethodssuchastheLempel-Zivfamilyareoftenpreferred.However,suchmethodscannotspeedupthepatternmatchingsinceanextraworkisneededtokeeptrackofcompressionmechanism.matchingパタンテキストKnuth-Morris-Pratt(1974)Boyer-Moo

5、re(1977)Aho-Corasick(1975)Shift-Or(1992)62001年度冬のLAシンポジウムAho-Corasick(AC)照合機械67891011121301234514rotherothem<>other任意の文字goto遷移failure遷移パタン集合：={other,}other72001年度冬のLAシンポジウム問題点タグ名の一部分とマッチする

あのTVCM

mothermを取った

6、らother、他人です．