タグ

algorithmとunixに関するtarchanのブックマーク (2)

  • いまさらgrepが10倍高速化したのはなぜか – はむかず!

    最近GNU grepコマンドの最新バージョンがリリースされ、速度が10倍になったとのアナウンスがあった。それを聞いて、なんであんな枯れた技術に10倍もの高速化の余地があったのだろうと不思議に思った人も多いだろう。 ニュース記事:grepコマンド最新版、”-i”で10倍の高速化 家のリリースノート:grep – News: grep-2.17 released [stable] 今回のリリースでは正確には、マルチバイトロケールで、-iオプション(–ignore-case、つまり大文字小文字を区別しないオプション)をオンにした時の速度が10倍くらいになったそうだ。 なぜそんなに速くなったのか?逆を言えば今までなぜそんなに遅かったのか? そもそも、多くの日人にとって「大文字小文字の区別」というと英語のアルファベットか、せいぜいフランス語とかドイツ語とかのアクサン記号・ウムラウトがついたものく

    tarchan
    tarchan 2014/02/26
    >マルチバイトロケールによっては、「大文字→小文字」または「小文字→大文字」の変換をすると文字のバイト数が変わってしまうことがある
  • 静かな注目を集める圧縮アルゴリズム「LZMA」

    GNUプロジェクトの配布アーカイブなどを中心に、LZMAを用いた圧縮形式を目にする機会が増えてきた。組み込み用途などへの活用も期待されるこの圧縮形式を紹介しよう。 2001年に開発された可逆圧縮アルゴリズム「LZMA」(Lempel-Ziv-Markov chain-Algorithm)が静かな注目を集めている。LZMAといえば、高い圧縮率を備え、Windowsアーカイバ「7-Zip」に採用されていることでも知られる。 ZIPやLHAなど、ファイルのアーカイブと圧縮が統合されているWindows由来のプログラムとは異なり、UNIXやLinuxでは伝統的にアーカイブと圧縮が個々のコマンドとして用意されており、それらを組み合わせて利用することになる。現在では、アーカイブがtar、圧縮にはGNU zip(.gz)やbzip2(.bz2)が併用されることが多い。 .gzや.bz2をしのぐ圧縮率が特

    静かな注目を集める圧縮アルゴリズム「LZMA」
    tarchan
    tarchan 2009/07/14
    LZMAは、算術符号の一種であり、整数で算術符号を実現したアルゴリズムをベースとする「Range Coder」が用いられている。/Range Coderは特許に抵触しない算術符号として捉えられている。
  • 1