記事情報殿堂入り企業

文字列アルゴリズムの学びかた

文字列アルゴリズムの学びかた

こんにちは!はてなアプリケーションエンジニアの id:takuya-a です。みなさんは、このような疑問をもったことはありませんか?grep はどのように文字列を検索しているのか?MeCab はどうやって辞書を高速にルックアップしているのか?パーサやコンパイラを作りたいけど、何から始めればいいのか?本稿では、「文字列アルゴリズムとはどんなものなのか?」「なぜ...

更新日: 2016-12-22
記事の見出し
  • 文字列アルゴリズムの学びかた
  • 文字列アルゴリズムとは
  • なぜ文字列アルゴリズムを学ぶのか
  • 最初に知っておくべきこと
  • どうやって勉強するか
  • 社内勉強会の取り組みについて
  • 代表的な文字列アルゴリズム
  • 1. Brute Force による文字列マッチング
  • 2. KMP による文字列マッチング
  • 3. BM (Boyer-Moore) による文字列マッチング
  • 4. Bitap (Shift-And / Shift-Or) アルゴリズムによる文字列マッチング
  • 5. Rabin-Karp (Rolling hash) による文字列マッチング
  • 6. トライ木 (Trie) による複数パターンマッチング
  • 7. 正規表現のマッチング
  • 8. 接尾辞配列 (Suffix Array)
  • 9. 接尾辞木 (Suffix Tree)
  • 10. BW 変換 (Burrows-Wheeler Transform)
  • 11. FM-index
  • 文字列アルゴリズムを実装するときのコツ
  • テストを書く
  • 簡単なものから実装する
  • マルチバイト文字の扱い
  • 番兵とヌル文字
  • さらに学ぶために
  • まとめ
テックブログ情報
文字列アルゴリズムの学びかた
ブログはてな開発者ブログ
ブログ概要はてな開発者ブログ
会社名株式会社はてな
会社概要『はてなブログ』『はてなブックマーク』などのサービスを提供しているテック企業です
上場情報Yahoo!ファイナンス