NLP

文法圧縮(6)

NLP

仕事上での悩みもあり、なかなかエンジンがかからない状態が続いており、新年からずっとダラダラしている。いまいちモチベーションが上がらないが、ずっとダラダラしていてもしょうがないので、簡単なことからいろいろとやり始めることとした。「遅くともや…

文法圧縮(5)

NLP

文法圧縮(Re-Pair)の構築部分については、線形時間で構築できるようになったが、文法圧縮部分の辞書をどう簡潔に保持するか?という問題が残っている。例えば、 abcabcabbという文字列に対して、Re-Pairを適用して、以下のような辞書(R)と圧縮文字列(C)が得…

Splunkを利用したテキストマイニングもどき

さて、前回の記事で、PerlからLTSV形式のフォーマットを扱う方法を書いた。http://rn.hatenablog.com/entry/2013/12/07/012621そのとき、自然言語処理の分野での適用をぼんやり考えていて、単語とか品詞とか簡単に集計できる仕組みがあると役立つかなと思っ…

文法圧縮(3)

NLP

落ち着いて作業できました。さて、前回、文法圧縮のRe-Pairを効率的に実装するのはなかなか難解だと書いたが、非常にシンプルに線形時間で実装できる論文を発見した。An Online Algorithm for Lightweight Grammar-Based Compression. Shirou Maruyama, Algo…

Wavelet TreeのTop-Kの改善

NLP

Wavelet Treeは強力なデータ構造ですが、ひとつどうしても気になる点があります。それは、Top-Kの列挙です。文字列本で紹介されているGreedyな方法は、結果がK件しか必要ないにもかかわらず、計算時間がけっこうかかります。他の操作は、最悪値の計算量が小…

文法圧縮(2)

NLP

休みは長かったけど、家の用事も多かったので、あまり論文を読むことができなかった。ただ、以前から少しずつ調査しているRe-Pairに関する論文を1本だけ読んだ。A fully linear-time approximation algorithm for grammar-based compression Hiroshi Sakamot…

Wavelet Treeをもう一度

NLP

文字列本のメインであるウェーブレット木をもう一度素直に見直すことにした。高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)作者: 岡野原大輔出版社/メーカー: 岩波書店発売日: 2012/12/27メディア: 単行本購入: 15人 …

高速な文字列マッチング

NLP

最近は、簡潔データ構造を中心に調べたりしていたけど、文字列マッチングを考えた場合、別のアプローチもあります。そう、grepのような逐次文字列検索ですね。以下の解説がおもしろいです。http://www.i.kyushu-u.ac.jp/~takeda/papers/IPSJMagazineCPM.pdfC…

高速文字列解析の"別"世界

NLP

1月に「高速文字列解析の世界」を購入してから半年が経ちました。以下、文字列本と呼びます。高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)作者: 岡野原大輔出版社/メーカー: 岩波書店発売日: 2012/12/27メディア: 単…

省メモリなBWT(2)

NLP

頭文字D 5th Stageを見ていたら、何もせずに土曜日が終わりそうです。絵がだいぶ変わっているが、ノリは変わってないので満足です。さて、本題です。 以下の論文を読んだので、そのことについてちょっとだけ書いておきます。文字列検索における圧縮インデッ…

文法圧縮(1)

NLP

ビットベクトルの完備辞書のさらなる圧縮のために、文法圧縮について調べている。かなり奥が深いようだ。自分のメモとして、調査したことをしばらく書いていく。Re-Pair(is the recursive replacements of all pairs)を応用した完備辞書を実装しようと思った…

省メモリなBWT

NLP

CSAやFM-Indexの構築時にボトルネックとなる省メモリなBWTの構築方法について調べた。実際、SAから構築する方法だとInduced Sortingを使うわけだが、最終的なCSAやFM-Indexの結果に比べてメモリを使いすぎる。これはちょっと嫌がられる。今はメモリが安いと…

文字列操作

NLP

こんな良書が出ていたとは知りませんでした。すぐに買いました。高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)作者: 岡野原大輔出版社/メーカー: 岩波書店発売日: 2012/12/27メディア: 単行本購入: 11人 クリック: 29…

Wikipediaからのテキスト抽出

NLP

個人レベルでいろいろテキストを解析して遊びたい時になかなか簡単に利用できるまとまったテキスト集合を入手しにくいです。 そんな時は、Wikipediaのテキストを利用しましょう。Wikipediaはかなりよくできたシステムであり、定期的に全記事をアーカイブして…

MeCabのipadic辞書への単語追加(ドメイン適応)

NLP

mecab-ipadicのCRF学習モデルが追加されたことにより、辞書に単語を追加しやすくなったようだ。http://sourceforge.jp/projects/mecab/lists/archive/users/2012-June/000456.html以前のMeCabの場合、単語追加をする場合は、追加したい単語と似ている単語の…

Backward Search

NLP

以下の論文で、Compressed Suffix Arrayについて全体を俯瞰した。 Compressed Full-Text Indexes. Navarro and Makinen, ACM Computing Surveys, 2007. http://www.cs.helsinki.fi/u/vmakinen/papers/survey.pdf 毎日の通勤の30分ぐらいで、少しずつ読み進め…

KyTea

NLP

KyTeaなる京都テキスト解析ツールキットを導入してみた。インストールはとても簡単で、私のCentOS 6.2の場合、以下のようないつもの手順でできました。 $ ./configure $ make # make installただ、私のOSが仮想マシンだからかなんだか知らないが、なんか遅い…

IR(3)

NLP

ようやく1章を読み終えた。 約30ページぐらいありました。 今は、2章の半ば、転置インデックスの基本的な話の部分を読んでいる。英語も非常に平易に書かれているので、辞書を引けば、だいたい理解できる。 内容も簡単なところから少しずつステップアップさせ…

ブログからのうつ傾向の解析

NLP

新幹線の中で、NLP2012の論文をつまみ読みしてみた。以下の論文が興味深かった。うつキーフレーズと感情変動に基づくブログからのうつ検出手法 松本, 吉岡, 北, 任, 言語処理学会第18回年次大会, 2012.実際に役立ちそうな可能性があるし、確かにブログやTwit…

IR(2)

NLP

以下の本をちょっとずつ読み進めています。Information Retrieval: Implementing and Evaluating Search Engines作者: Stefan Buettcher,Charles L. A. Clarke,Gordon V. Cormack出版社/メーカー: The MIT Press発売日: 2010/07/23メディア: ハードカバー購…

IR(1)

NLP

基本、我流で論文読んだり、雑誌読んだり、ネットの解説読んだりして、情報を仕入れてやってきましたが、今年はまともに勉強しようと2月に決めたので、評判が良かった以下の本を買ってみました。Information Retrieval: Implementing and Evaluating Search …

SA

NLP

最近、英語の論文で情報を収集しています。 ほんとは読みたくないけど、そこにしか情報がないので。 読みなれていないので、かなりストレスですがね。 脳みその普段使ってない部分を使っているのか、めっちゃ疲労します。さて、最近は、CSAやFM-IndexなどのS…

KNPのインストール

NLP

Jumanに引き続きKNPのインストールについても書いてみます。 この記事はKNPのバージョン4について書いています。こちらは、私の環境(CentOS 6.2)では素直にできなかったので、多少めんどくさいかもしれません。インストールファイルのダウンロードなどは、Ju…

Jumanのインストール

NLP

Jumanも気づけばバージョン7ですか。 私が最初に使ったのは、バージョン3だったか4だったかぐらいでしたね。 当時、大学1年生でした。 ウェブ上の解説を見ながら、一週間ぐらいかけてインストールしました。 当時は、Linuxの知識が皆無だったので苦労しまし…