akimachoのはてなブログ

ICTとデザインのためのブログ

黒橋 禎夫『自然言語処理』第2章メモ

はじめに

黒橋 禎夫『自然言語処理』第2章のメモです。

文字コード

プログラマのための文字コード技術入門』を読んでいたので、大体のことは把握していました。

プログラマのための文字コード技術入門 (WEB+DB PRESS plus) (WEB+DB PRESS plusシリーズ)

プログラマのための文字コード技術入門 (WEB+DB PRESS plus) (WEB+DB PRESS plusシリーズ)

文字列の探索

正規表現やKMP法をとりあげるのかと思ったら、違ってました。

「探索」とは以下のようなことを指すようです。

自然言語においても、単語あるいは文字列(キー)に対する種々の情報(バリュー)をコンピュータに保存しておき、これを取り出して利用することが頻繁に行われる。 このような処理を探索(search)と呼ぶ。p.28

メモとして、アルゴリズムの特徴や性質をまとめておきます。

ハッシュ(hash)法

衝突(collision)対策のアルゴリズム

  • チェイン法(chaining) ― 連結リストを用いる。探索・挿入・削除 O(1)
  • オープンアドレス法(open addressing) ― 再ハッシュを行う。計算量の計算はちょっと複雑なので省略

wikipedia

トライ(trie)法

いくつかの本に書かれていたので、あとでまとめます。

wikipedia

感想

ハッシュ法は「データ構造とアルゴリズム」の講義で習いましたが、トライ法は知りませんでした。宿題として、Pythonでハッシュ法とトライ法を実装しておきたいと思います。

自然言語処理 (放送大学教材)

自然言語処理 (放送大学教材)

参考になりそうなリンク集