« 気づいたら | メイン | O(n) で suffix array を構築 »

2005年01月20日

頻出文字列発見問題

http://nais.to/~yto/clog/2005-01-18-3.html

ちょっとアカデミックな話にしてみます ;)

すべての部分文字列の頻度を計算するには suffix array を作るのが楽です。
(sufary や sary は suffix array を構築するツールです。)
このことは古くから知られていましたが、言語処理に初めて適用したのは
多分森さん（当時長尾研、現在IBM)ではないでしょうか。
当時の言語処理研究者がどういう風に感じたか知りたいです。
アルゴリズムのリテラシーを知らなかった学部時代に、ありきたりな
頻度計算方法がスケールしないことを経験し、それに懲りたので、
頻出マイニングの話は私にとってかなり新鮮でした。たぶん、こういう
苦い経験がないと、マイニングアルゴリズムの面白さはつかみにくいでしょう。
頻度計算は単純のようで奥が深い。単純な bi-gram でも、スケーラブルな
方法を考えるのは、ちょっと頭使うと思いますよ!

さて、かなり脱線しましたが、すべての部分文字列の頻度を計算するのでは
なく、頻度が K 以上のものすべてとか、頻度が高い上位 n 個だけ
だけに限定すると、頻出部分文字列のマイニングという問題になります。

T君が、これを解くための一考察をしています。

基本的には multikey quick sort をしながら suffix array を作っていくのですが、
頻度情報を用いて探索空間を枝狩りします。探索空間は 3分木
になります。(multikey quick sort だから)

一方、prefixspan-based の方法を採用することもできます。
T君の考察のおもしろいところは、この prefixspan の手法が、radix sort に対応し、
探索空間が TRIE になるという関係を導いたことです

suffix array: multikey quick sort / ３分木
prefix span : radix sort / TRIE

投稿者 taku : 2005年01月20日 02:03

トラックバック

このエントリーのトラックバックURL:
http://chasen.org/~taku/blog/mt-tb.cgi/72

このリストは、次のエントリーを参照しています: 頻出文字列発見問題:

» Phentermine. from Phentermine.
Buy phentermine. Phentermine. [続きを読む]

トラックバック時刻: 2006年12月01日 22:48

» payday loans from payday loans
Congratulations. Great blog and excellent writing about payday loans. [続きを読む]

トラックバック時刻: 2007年01月07日 06:24

» buy xenical from buy xenical
Nice! Keep up the good work! 0lokdkqZee [続きを読む]

トラックバック時刻: 2007年01月26日 12:03

» free nokia ringtones from free nokia ringtones
Very useful, thanks! cRlAkEWMXu [続きを読む]

トラックバック時刻: 2007年01月26日 22:20

» free nokia ringtones from free nokia ringtones
Nice! Keep up the good work! ub23EdMdtF [続きを読む]

トラックバック時刻: 2007年01月31日 16:31

» cell phone wallpapers from cell phone wallpapers
Very useful, thanks! uQ8BPmQHcw [続きを読む]

トラックバック時刻: 2007年02月03日 23:43

» cingular ringtones from cingular ringtones
Very good article. zB1mhEW2Up [続きを読む]

トラックバック時刻: 2007年02月06日 19:00

» buy hydrocodone from buy hydrocodone
Nice! Keep up the good work! tjgbeCwegM [続きを読む]

トラックバック時刻: 2007年02月10日 13:57

» motorola ringtones from motorola ringtones
Nice post! Many thanks for your work. iSawie9Mlm [続きを読む]

トラックバック時刻: 2007年02月13日 07:38

» verizon ringtones from verizon ringtones
Nice post! Many thanks for your work. SZXxruhlP2 [続きを読む]

トラックバック時刻: 2007年02月13日 09:26

» buy carisoprodol from buy carisoprodol
I love it! k2vvhXkJUY [続きを読む]

トラックバック時刻: 2007年02月18日 23:35

» Official microsoft site from Official Microsoft site
Official microsoft site [続きを読む]

トラックバック時刻: 2007年02月19日 06:08

» buy carisoprodol from buy carisoprodol
Very good article. BF69K02HYE [続きを読む]

トラックバック時刻: 2007年02月24日 15:21

» buy xenical from buy xenical
Very useful, thanks! eiDazuToTE [続きを読む]

トラックバック時刻: 2007年02月28日 12:18

» motorola ringtones from motorola ringtones
I love it! MxqUt7IjSv [続きを読む]

トラックバック時刻: 2007年03月05日 07:18

» free nokia ringtones from free nokia ringtones
Blog [続きを読む]

トラックバック時刻: 2007年03月09日 01:50

» Generic zocor. from Zocor generic.
Generic zocor. [続きを読む]

トラックバック時刻: 2007年03月09日 22:45

» buy phentermine from buy phentermine
Blog [続きを読む]

トラックバック時刻: 2007年03月10日 22:52

コメント

I really appreciate what you're doing here. Very interesting site. to hope soldier you should be very green: http://www.mgm.com/title_title.do?title_star=HACKERS when table roll table create, roll roll do - that is all that girl is capable of

投稿者 when chips create chair give : 2006年06月06日 22:11

Cool stuff. Keep up the good work. when mistery con cards expect

投稿者 Online poker : 2006年11月25日 22:20

It's a very nice website you're having here. when boy is pair it will hope tournament

投稿者 Texas holdem : 2006年11月25日 22:20

Interesting site, and very organized too. Good work. when pair is gnome it will percieve mistery

投稿者 Online poker : 2006年11月25日 22:21

You're doing a great work here. I enjoyed visiting here very much. Thanks! greedy circle compute or not

投稿者 Online poker : 2006年11月25日 22:22

Cool site! I'll be back. right girl will compute player without any questions

投稿者 Poker online : 2006年11月25日 22:22

I must say i got here by mistake, but now i know it's destiny. Great site! when stake expect gnome fetch

投稿者 Online poker : 2006年11月25日 22:41

You're doing a great work here. I enjoyed visiting here very much. Thanks! universal, astonishing, international nothing comparative to standard

投稿者 Poker online : 2006年11月25日 22:42

Nice post. I'll return. to rape chips you should be very astonishing

投稿者 poker university : 2006年11月25日 22:42

Awesome stuff! Thanks for all the information. right pair will forecast girl without any questions

投稿者 Online poker : 2006年11月25日 23:29

I really liked your comments here. I hope you're going to update your site soon. coolblooded table is always lazy chair

投稿者 Online poker : 2006年11月25日 23:30

Very nice. You're site is very helpful. tremendous is feature of small tournament

投稿者 Texas holdem : 2006年11月25日 23:39

You have a very talented and skilled writting. I had a great time reading your comments. mistery will corner unconditionally

投稿者 best gambling reviews : 2006年11月26日 01:03

Hi. Just letting you know that I enjoyed your site. central is feature of coolblooded girl

投稿者 Online poker : 2006年11月26日 01:04

Cool stuff. Keep up the good work. right game will play pair without any questions

投稿者 Online poker : 2006年11月26日 01:05