Thursday, September 13, 2007

Knowledge extraction with 2 dimensional regular expressions?

Some of my best and worst ideas come when I'm sitting on the toilet. I pretty much have an informal bookshelf next to it, which I use to refresh and reinforce my memories of galois theory, probability, or in this case, automata from time to time. I'm not getting any younger (almost 36) -- it's been ages since college -- so whatever time I can use to reinforce those neurons and keep those skills from slipping away is golden.

So, there I was, automata book in hand, thinking about how I could simplify and modularize, Tardis, Timepedia's web crawler, automated knowledge discovery extractor, and temporal query engine. One part of what Tardis does is look for time related information in documents, and extract timeseries and timeline information.

How it does this exactly, I won't say at this time, but it uses a large battery of heuristics and other classical algorithms. The problem is, this logic is cemented inside of Java code, a sort of implicit 'expert system' with a huge number of cases, and complex interactions. Extending this to support newly discovered rules is hard enough with the source code in hand, but impossible for the end user.

Wouldn't a DSL be better? But if so, which one? An expert system like CLIPS/JESS? Those risk alot of complexity as well as scalability issues. If this was simple text extraction, I'd give the users the ability to author custom regexp match/rewrite rules for particular documents, sort of a mini-online-SED. As you can imagine, a lot of time related information is two dimensional in nature, stored in documents in tabular form, so ordinary regexp's don't capture the problem.

Aha! What about two dimensional regular expressions? Do they even exist? By the time I had gotten off the toilet, I had already devised replacements for regular expression concatenation operators in the form of row/column concatenation operators. I knew however that I was not the first to think of this, so a quick Google Scholar search led me to this paper: Two-Dimensional Languages (1997), Dora Giammarresi, Antonio Restivo, Handbook of Formal Languages

At first glance, this looks like a fertile field, previously applied for recognizing graphical features in pictures. Could I extend it to my needs? More on that later. First, let's look at an example.

As you may recall, a classical regular expression consists of operations like concatenation, union, and Kleene star. Concatenation is usually represented by placing two symbols next to one another, such as "ab" which means "a + b" where + is the concatenation operation. Union is typically represented via the pipe character "|", so "a|b" means "a union b". Kleene star of course is the union of all possible concatenations, e.g. "(a|b)*" = e, a, b, a+b, a+a, b+b, aa+b, ab+a, etc.

The two dimensional analogues of these would row concatenation, column concatenation, and row/column Kleene star operators. Let us denote column concatenation as "+", and row concatenation as "/", so "a + b" recognizes "ab" as long as they are in the same row, and "a/b" recognizes "ab" as long as they are in the same column. Column-wise Kleene star as "+*" and row wise Kleene star as "/*".

Now let's try a problem, recognize the set of all "chessboards", encoded with the symbols 'b' for black, and 'w' for white squares. Here's an example chessboard:


b w b w b w b w
w b w b w b w b
b w b w b w b w
w b w b w b w b
...


First, we match the first row with "(b + w)+*". Next, we match the second row with "(w + b)+*", and then we concatenate these two expressions row wise, to form

"(b + w)+* / (w + b)+*"

This says match "bwbwbw..." followed on the next row by "wbwbwb...". Now all we've got to do is repeat this pattern row rise.

"( (b + w)+* / (w + b)+) )/*"

This will match the above chessboard pattern. I realize it may be confusing to represent column wise concatenation via '+' instead of the empty string as is traditional, but I wanted to make the separate row and column operators explicit and equal in importance.

Now, I was delighted that something like this could be done, and furthermore that theoretical results for NFAs, DFAs, and closure properties existed for such languages, but I still faced the problem that knowledge extraction seems to require processing values semantically, not just lexically, so I tabled it as just a nifty and cool area of research, but with no application to what we were doing.

That was, until I showed it to Mat, who came up with an additional step that would enabled 2D regexps such as those described above to be used by Tardis for time related extraction. And that story, I will leave for a future article. :) The lesson I learned however, is not to give up on an idea that may seem impractical until you've got input from other people.

In the mean time, check out the paper I linked.

-Ray

8 comments:

Cristian George said...

I fail to understand how you can call this thing a 2-dimensional regular expression.

The example you provided treats the "text" as a continuous, 1D, stream of bytes. Just insert \n in the regular expression to mark the end of a row and you'll be matching chess boards immediately.


Try to design a 2D regular expression that matches rectangular areas of vowels. Make sure to test it with multiple rectangles that intersect column-wise, but not row-wise.

Ray Cromwell said...

It is certainly a 2-dimensional regular expression, the fact that the language it is recognizing (l in L such that l is a chessboard) may be recognized by 1-dimensional regular expression does not detract from that, anymore than if I design a context free grammar to recognize the language "abababab", does not mean the grammar isn't a CFG, it just means the language "abababab" doesn't require a CFG to accept it.

Perhaps it's a poorly chosen trivial example, but it's not my example, it's the first example given in the paper I cited. There are other more complex examples in the paper if you take a look.

sexy said...

情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣,情趣,情趣,情趣,情趣,情趣,情趣用品,情趣用品,情趣,情趣,A片,A片,A片,A片,A片,A片,情趣用品,A片,情趣用品,A片,情趣用品,a片,情趣用品,視訊聊天室,聊天室,視訊,ut聊天室,聊天室,視訊聊天室,成人電影,

A片,A片,AV女優,色情,成人,做愛,情色,AIO,視訊聊天室,SEX,聊天室,自拍,AV,情色,成人,情色,aio,sex,成人,情色,色情,情色電影,色情網站,av女優,av,自拍,成人,視訊聊天室,視訊交友網,AV女優,成人,聊天室,ut聊天室,av女優

免費A片,美女視訊,情色交友,免費AV,色情網站,辣妹視訊,美女交友,色情影片,成人影片,成人網站,H漫,18成人,成人圖片,成人漫畫,情色網,日本A片,免費A片下載,性愛

色情A片,A片下載,色情遊戲,色情影片,色情聊天室,情色電影,免費視訊,免費視訊聊天,免費視訊聊天室,一葉情貼圖片區,情色視訊,免費成人影片,視訊交友,視訊聊天,言情小說,愛情小說,AV片,A漫,av dvd,情色論壇,視訊美女,AV成人網,情色文學,成人交友,成人電影,成人貼圖,成人小說,成人文章,成人圖片區,成人遊戲,愛情公寓,情色貼圖,成人論壇,色情


微風成人,嘟嘟成人網,成人貼圖,成人交友,成人圖片,18成人,成人小說,成人圖片區,成人文章,成人影城,愛情公寓,情色,情色貼圖,色情聊天室,情色視訊,情色文學,色情小說,情色小說,寄情築園小遊戲,情色電影,aio,av女優,AV,免費A片,日本a片,美女視訊,辣妹視訊,聊天室,美女交友,成人光碟

said...

A片,A片,成人網站,成人漫畫,色情,情色網,情色,AV,AV女優,成人影城,成人,色情A片,日本AV,免費成人影片,成人影片,SEX,免費A片,A片下載,免費A片下載,做愛,情色A片,色情影片,H漫,A漫,18成人

a片,色情影片,情色電影,a片,色情,情色網,情色,av,av女優,成人影城,成人,色情a片,日本av,免費成人影片,成人影片,情色a片,sex,免費a片,a片下載,免費a片下載

情趣用品,情趣用品,情趣,情趣,情趣用品,情趣用品,情趣,情趣,情趣用品,情趣用品,情趣,情趣

A片,A片,A片下載,做愛,成人電影,.18成人,日本A片,情色小說,情色電影,成人影城,自拍,情色論壇,成人論壇,情色貼圖,情色,免費A片,成人,成人網站,成人圖片,AV女優,成人光碟,色情,色情影片,免費A片下載,SEX,AV,色情網站,本土自拍,性愛,成人影片,情色文學,成人文章,成人圖片區,成人貼圖

情色,AV女優,UT聊天室,聊天室,A片,視訊聊天室

一夜情聊天室,一夜情,情色聊天室,情色,美女交友,交友,AIO交友愛情館,AIO,成人交友,愛情公寓,做愛影片,做愛,性愛,微風成人區,微風成人,嘟嘟成人網,成人影片,成人,成人貼圖,18成人,成人圖片區,成人圖片,成人影城,成人小說,成人文章,成人網站,成人論壇,情色貼圖,色情貼圖,色情A片,A片,色情小說,情色小說,情色文學,寄情築園小遊戲, 情色A片,色情影片,AV女優,AV,A漫,免費A片,A片下載

信次 said...

情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,美國aneros,rudeboy,英國rudeboy,英國Rocksoff,德國Fun Factory,Fun Factory,英國甜筒造型按摩座,甜筒造型按摩座,英國Rock Chic ,瑞典 Lelo ,英國Emotional Bliss,英國 E.B,荷蘭 Natural Contours,荷蘭 N C,美國 OhMiBod,美國 OMB,Naughti Nano ,音樂按摩棒,ipod按摩棒,美國 The Screaming O,美國TSO,美國TOPCO,美國Doc Johnson,美國CA Exotic,美國CEN,美國Nasstoy,美國Tonguejoy,英國Je Joue,美國Pipe Dream,美國California Exotic,美國NassToys,美國Vibropod,美國Penthouse,仿真按摩棒,矽膠按摩棒,猛男倒模,真人倒模,仿真倒模,PJUR,Zestra,適趣液,穿戴套具,日本NPG,雙頭龍,FANCARNAL,日本NIPPORI,日本GEL,日本Aqua Style,美國WET,費洛蒙,費洛蒙香水,仿真名器,av女優,打炮,做愛,性愛,口交,吹喇叭,肛交,魔女訓練大師,無線跳蛋,有線跳蛋,震動棒,震動保險套,震動套,TOY-情趣用品,情趣用品網,情趣購物網,成人用品網,情趣用品討論,成人購物網,鎖精套,鎖精環,持久環,持久套,拉珠,逼真按摩棒,名器,超名器,逼真老二,電動自慰,自慰,打手槍,仿真女郎,SM道具,SM,性感內褲,仿真按摩棒,pornograph,hunter系列,h動畫,成人動畫,成人卡通,情色動畫,情色卡通,色情動畫,色情卡通,無修正,禁斷,人妻,極悪調教,姦淫,近親相姦,顏射,盜攝,偷拍,本土自拍,素人自拍,公園露出,街道露出,野外露出,誘姦,迷姦,輪姦,凌辱,痴漢,痴女,素人娘,中出,巨乳,調教,潮吹,av,a片,成人影片,成人影音,線上影片,成人光碟,成人無碼,成人dvd,情色影音,情色影片,情色dvd,情色光碟,航空版,薄碼,色情dvd,色情影音,色情光碟,線上A片,免費A片,A片下載,成人電影,色情電影,TOKYO HOT,SKY ANGEL,一本道,SOD,S1,ALICE JAPAN,皇冠系列,老虎系列,東京熱,亞熱,武士系列,新潮館,情趣用品,情趣,情趣商品,情趣網站,跳蛋,按摩棒,充氣娃娃,自慰套,G點,性感內衣,情趣內衣,角色扮演,生日禮物,生日精品,自慰,打手槍,潮吹,高潮,後庭,情色論譠,影片下載,遊戲下載,手機鈴聲,音樂下載,開獎號碼,統一發票號碼,夜市,統一發票對獎,保險套,做愛,減肥,美容,瘦身,當舖,軟體下載,汽車,機車,手機,來電答鈴,週年慶,美食,徵信社,網頁設計,網站設計,室內設計,靈異照片,同志,聊天室,運動彩券,大樂透,威力彩,搬家公司,除蟲,偷拍,自拍,無名破解,av女優,小說,民宿,大樂透開獎號碼,大樂透中獎號碼,威力彩開獎號碼,討論區,痴漢,懷孕,美女交友,交友,日本av,日本,機票,香水,股市,股市行情, 股市分析,租房子,成人影片,免費影片,醫學美容,免費算命,算命,姓名配對,姓名學,姓名學免費,遊戲,好玩遊戲,好玩遊戲區,線上遊戲,新遊戲,漫畫,線上漫畫,動畫,成人圖片,桌布,桌布下載,電視節目表,線上電視,線上a片,線上掃毒,線上翻譯,購物車,身分證製造機,身分證產生器,手機,二手車,中古車,法拍屋,歌詞,音樂,音樂網,火車,房屋,情趣用品,情趣,情趣商品,情趣網站,跳蛋,按摩棒,充氣娃娃,自慰套, G點,性感內衣,情趣內衣,角色扮演,生日禮物,精品,禮品,自慰,打手槍,潮吹,高潮,後庭,情色論譠,影片下載,遊戲下載,手機鈴聲,音樂下載,開獎號碼,統一發票,夜市,保險套,做愛,減肥,美容,瘦身,當舖,軟體下載,汽車,機車,手機,來電答鈴,週年慶,美食,徵信社,網頁設計,網站設計,室內設計,靈異照片,同志,聊天室,運動彩券,,大樂透,威力彩,搬家公司,除蟲,偷拍,自拍,無名破解, av女優,小說,民宿,大樂透開獎號碼,大樂透中獎號碼,威力彩開獎號碼,討論區,痴漢,懷孕,美女交友,交友,日本av ,日本,機票,香水,股市,股市行情,股市分析,租房子,成人影片,免費影片,醫學美容,免費算命,算命,姓名配對,姓名學,姓名學免費,遊戲,好玩遊戲,好玩遊戲區,線上遊戲,新遊戲,漫畫,線上漫畫,動畫,成人圖片,桌布,桌布下載,電視節目表,線上電視,線上a片,線上a片,線上翻譯,購物車,身分證製造機,身分證產生器,手機,二手車,中古車,法拍屋,歌詞,音樂,音樂網,借錢,房屋,街頭籃球,找工作,旅行社,六合彩,整型,整型,珠海,雷射溶脂,婚紗,網頁設計,水噹噹,台中隆鼻,果凍隆乳,改運整型,自體脂肪移植,新娘造型,婚禮顧問,下川島,常平,常平,珠海,澳門機票,香港機票,貸款,貸款,信用貸款,宜蘭民宿,花蓮民宿,未婚聯誼,網路購物,婚友,婚友社,未婚聯誼,交友,婚友,婚友社,單身聯誼,未婚聯誼,未婚聯誼, 婚友社,婚友,婚友社,單身聯誼,婚友,未婚聯誼,婚友社,未婚聯誼,單身聯誼,單身聯誼,白蟻,白蟻,除蟲,老鼠,減肥,減肥,在家工作,在家工作,婚友,單身聯誼,未婚聯誼,婚友,交友,交友,婚友社,婚友社,婚友社,大陸新娘,大陸新娘,越南新娘,越南新娘,外籍新娘,外籍新娘,台中坐月子中心,搬家公司,搬家公司,中和搬家,台北搬家,板橋搬家,新店搬家,線上客服,網頁設計,線上客服,網頁設計,植牙,關鍵字,關鍵字,seo,seo,網路排名,自然排序,網路排名軟體,交友,越南新娘,婚友社,外籍新娘,大陸新娘,越南新娘,交友,外籍新娘,視訊聊天,大陸新娘,婚友社,婚友,越南新娘,大陸新娘,越南新娘,視訊交友,外籍新娘,網路排名,網路排名軟體,網站排名優化大師,關鍵字排名大師,網站排名seo大師,關鍵字行銷專家,關鍵字,seo,關鍵字行銷,網頁排序,網頁排名,關鍵字大師,seo大,自然排名,網站排序,網路行銷創業,汽車借款,汽車借錢,汽車貸款,汽車貸款,拉皮,抽脂,近視雷射,隆乳,隆鼻,變性,雙眼皮,眼袋,牙齒,下巴,植牙,人工植牙,植髮,雷射美容,膠原蛋白,皮膚科,醫學美容,玻尿酸,肉毒桿菌,微晶瓷,電波拉皮,脈衝光,關鍵字,關鍵字,seo,seo,網路排名,自然排序,網路排名軟體,汽車借款,汽車借款,汽車借款,汽車貸款,汽車貸款,借錢,借貸,當舖,借款,借貸,借錢,週轉,學英文,英文社團,英語俱樂部,學習英文,英語會話,英文演講,English Club,學英語,學英文,美語社團,英語社團,英文讀書會,Toastmasters,Toastmaster,英語讀書會,拍樂得批發,拍樂得飾品,拍樂得化妝品批發,

正享 said...

專業合法驅除
白蟻
除白蟻
白蟻防治
跳蚤
除跳蚤
跳蚤防治
蛀蟲
除蛀蟲
蛀蟲防治
白蟻
除白蟻
白蟻防治
跳蚤
除跳蚤
跳蚤防治
蛀蟲
除蛀蟲
蛀蟲防治
除蟲
除蟲
歡迎參閱

商標打人 said...

當舖
專利
專利
關鍵字
專利
當舖
存證信函
存證信函
關鍵字
存證信函
當舖
商標
商標設計
自創品牌
商標
關鍵字
商標
當舖

平平 said...

^^ nice blog!! ^@^

徵信, 徵信網, 徵信社, 徵信社, 徵信社, 徵信社, 感情挽回, 婚姻挽回, 挽回婚姻, 挽回感情, 徵信, 徵信社, 徵信, 徵信, 捉姦, 徵信公司, 通姦, 通姦罪, 抓姦, 抓猴, 捉猴, 捉姦, 監聽, 調查跟蹤, 反跟蹤, 外遇問題, 徵信, 捉姦, 女人徵信, 女子徵信, 外遇問題, 女子徵信, 徵信社, 外遇, 徵信公司, 徵信網, 外遇蒐證, 抓姦, 抓猴, 捉猴, 調查跟蹤, 反跟蹤, 感情挽回, 挽回感情, 婚姻挽回, 挽回婚姻, 外遇沖開, 抓姦, 女子徵信, 外遇蒐證, 外遇, 通姦, 通姦罪, 贍養費, 徵信, 徵信社, 抓姦, 徵信社, 徵信, 徵信公司, 徵信社, 徵信, 徵信公司, 徵信社, 徵信公司, 女人徵信, 外遇

徵信, 徵信網, 徵信社, 徵信網, 外遇, 徵信, 徵信社, 抓姦, 徵信, 女人徵信, 徵信社, 女人徵信社, 外遇, 抓姦, 徵信公司, 徵信社, 徵信社, 徵信社, 徵信社, 徵信社, 徵信社, 女人徵信社, 徵信社, 徵信, 徵信社, 徵信, 女子徵信社, 女子徵信社, 女子徵信社, 女子徵信社, 徵信, 徵信社, 徵信, 徵信社, 徵信, 徵信社, 徵信, 徵信社, 徵信, 徵信社, 徵信, 徵信社, 徵信社,

徵信, 徵信社,徵信, 徵信社, 徵信, 徵信社, 徵信, 徵信社, 徵信, 徵信社, 徵信, 徵信社, 徵信, 徵信社, 徵信, 徵信社, 徵信, 徵信社, 徵信, 徵信社, 徵信, 徵信社, 徵信, 徵信社, 徵信, 徵信社, 徵信, 徵信社, 徵信, 徵信社, 徵信, 徵信社, 徵信, 徵信社, 外遇, 抓姦, 離婚, 外遇,離婚,

徵信, 外遇, 離婚, 徵信社, 徵信, 外遇, 抓姦, 徵信社, 徵信, 徵信社, 徵信, 外遇, 徵信社, 徵信, 外遇, 抓姦, 徵信社, 征信, 征信, 徵信, 徵信社, 徵信, 徵信社, 征信, 徵信, 徵信社, 徵信, 徵信社, 徵信, 徵信社, 徵信, 徵信社, 徵信社, 徵信社, 徵信, 外遇, 抓姦, 徵信, 徵信社, 徵信, 徵信社, 徵信,