Subscribed unsubscribe Subscribe Subscribe

Hatena Developer Blog

はてな開発者ブログ

「バックログに入らないタスクを可視化する仕組み」という話を技術勉強会でしました

こんにちは。アプリケーションエンジニアの id:daiksy です。

はてなでは毎週木曜日に技術勉強会を開催しています。

参考: 寿司と勉強会とエンジニア - Hatena Developer Blog

先週、当番が回ってきたので、「バックログに入らないタスクを可視化する仕組み」というトークをしました。

speakerdeck.com

詳細はスライドを見ていただくとして、この発表で定義された「税」などの用語が、さっそく社内でのコミュニケーションでも使われだして、エンジニア同士で、ある概念について共通の認識を持つためにもこういった場は効果があるな、と実感しました。

はてなでは、アプリケーションを構築する技術だけではなく、プロジェクトマネジメントやチームビルディングの知見などもこうして技術勉強会で共有されています。

学生さん向け「はてな&Wantedly 合同説明会」1月25日(水)に東京で開催します!

はてなは1月25日(水)に、エンジニア志望の学生さん向けにWantedlyさんと合同で会社説明会を開催します。

今回は会社説明だけでなく、エンジニア社員が普段どういう風に働いているのか をより知っていただく機会にするため、飲食を交えながらエンジニア社員と密に話ができる場を設けます。 当日ははてなとWantedlyさんのエンジニア社員で6つのブースをつくり、参加者はそれぞれのブースに交代で回っていただきます。

普段はあまり接することのない社員とざっくばらんに話す機会を通して我々やWantedlyさんについて深く知ることが出来る機会となっています。2社に少しでも興味のあるエンジニア学生さんは是非お越しください!

イベント日程と会場

  • イベント名: はてな&Wantedly 合同説明会
  • 対象:エンジニア志望の学生さん(くわしい応募要件は申し込みページをご覧ください)
  • 日時: 1月25日(水) 19:00-21:00(18:45 受付開始 / 懇親会含む)
  • 参加費: 無料
  • 定員:30名(応募者多数の場合は抽選とさせていただきます)
  • 会場:ウォンテッドリー白金台オフィス
    • 所在地:東京都港区白金台5-12-7 MG白金台ビル4階

当日参加予定の社員紹介

はてな

  • 大坪 弘尚(id:motemen / @motemen)
    • 株式会社はてな 最高技術責任者。 2008年、アプリケーションエンジニアとして、はてなに新卒入社し、はてなの新サービス開発に数多く関わる。2016年に最高技術責任者に就任。現在ははてなのプラットフォームでアプリケーションエンジニアとして業務に携わりつつ、技術組織全般の統括を行っている。
    • https://www.wantedly.com/users/12432
  • 松木 雅幸(id:Songmu / @songmu)
    • 慶應義塾大学環境情報学部で中国語と機械翻訳の研究に注力。卒業後中国へ渡り、ITベンチャーの立ち上げに関わる。その後に帰国し、印刷系SIerでの業務、カヤックでソーシャルゲーム開発のリードエンジニアなどの経験を経て、2014年9月にはてなに入社。東京オフィスでチーフエンジニアを務めるとともに、Mackerelというサーバー監視SaaSのディレクターを担当している。最近はGo言語がお気に入りで「みんなのGo言語」という本を共著で執筆しました。
    • https://www.wantedly.com/users/11167
  • 和田 将義 (id:masawada / @masawada)
    • 株式会社はてな Webアプリケーションエンジニア。 電気通信大学情報理工学部在学中に、はてなサマーインターン2014に参加。後にアルバイトを経て2016年に新卒入社。現在は、はてなブログチームで新機能の提案および開発を行う。
    • https://www.wantedly.com/users/313960

Wantedly

  • 川崎 禎紀 (@kawasy)
    • Wantedly 取締役CTO。 2012年4月よりビジネスSNS「Wantedly」の開発・ 運営に参画。開発、マーケ、採用・育成など、プロ ダクトと組織づくりに幅広く携わる。
    • https://www.wantedly.com/users/10599
  • 坂部 広大 (@koudaiii)
    • Wantedly インフラエンジニア。 Wantedlyインフラチームでサービス基盤の改善とツール開発に従事。「Docker を Production で使い続ける理由」(Wantedly Engineer Blog)、「Docker と Kubernetes を使って変化に強いインフラを作る」(Wantedly Engineer Blog)など、変化に強いインフラ作りに日々取り組んでいる。
    • https://www.wantedly.com/users/310906
  • 森脇 健斗 (@Kento_Moriwaki)
    • Wantedly 新卒二年目エンジニア。 大阪大学工学部を卒業後、Wantedlyに新卒入社。フィードチームとインターナショナルチームとして、施策を考えるところから開発まで、幅広く取り組んでいる。フロントエンドが好きで、WantedlyにReactを導入した。
    • https://www.wantedly.com/users/1468880

タイムスケジュール

時間 内容
18:45-19:00 開場
19:00-19:20 2社による会社説明
19:20-20:20 エンジニア交流会 (参加者同士でグループを設定させていただき、10分毎に6つのブースを回ります)
20:20-21:00 懇親会(軽食をご用意してあります)

※ 内容を変更する可能性があります

お申し込み方法

以下のページからお申し込みください。

wantedly.connpass.com

はてなサマーインターン2016のレポートサイトを公開しました

2016年8月15日から9月9日まで開催された、「はてなサマーインターン2016」のレポートサイトを公開しました。

はてなサマーインターンシップは、はてなでのサービス開発や研究を体験できる、学生向けのインターンシッププログラムです。カリキュラム前半の講義でWebサービス開発の基礎知識を身に付け、カリキュラム後半で開発チームの一員となってはてなが提供する各サービスの開発に取り組みます。これらの体験を通して、Webサービス開発者に必要となる知識と経験を得て、技術者として大きく成長してもらうことを目的としています。

レポートサイトでは、インターン生が過ごした20日間の様子や、はてなのサービスでどんな機能を開発したのかを紹介しています。今年は機械学習の講義や、特別講義のAWSハンズオンなど新しい試みも多く取り入れました。これらの詳細をぜひレポートサイトでご覧になっていただければと思います。次回以降のインターンに興味がある学生の皆さんも、ぜひご覧ください!

インターンシップ以外に、はてなではアルバイトも募集しています。はてなインターンシップに準じた教育プログラムで学んでいただいた後、はてなの各サービスに開発者として携わっていただきます。はてなで技術的に成長したい方の応募をお待ちしております!

2016年はてなWebオペレーションエンジニアのアウトプット

こんにちは、シニアエンジニアの id:y_uuki です。 はてなのWebオペレーションエンジニア8名が、この1年で対外的にアウトプットした成果物をまとめて紹介します。

座談会

今週、Webオペレーションエンジニアの座談会記事を公開しました。技術ブログや技術発表では表現しきれない一人一人の考え方や思いが垣間見えるコンテンツになっていると思います。

Software Engineering

Keepalivedのシンタックスチェッカ「gokc」を作った - ゆううきブログ

gokcというGoで作られたKeepalivedの設定ファイルのシンタックスチェッカーです。社内で普通に導入しています。

インフラエンジニアがGo言語でオペレーションツールを書くことについて - Hatena Developer Blog

Go 1.6 Release Partyでの発表内容です。Go言語が好き。

自作Linuxコンテナの時代 - ゆううきブログ Droot Internals // Speaker Deck

自分の用途にあったLinuxコンテナエンジンを自作しようみたいな話です。第9回コンテナ型仮想化の情報交換会@福岡での発表がベースになっています。

CPAN Authorになった (Pgtoolsリリースした) - tom__bo’s Blog

はてなインターン2015で作ってもらっていたPostgresの運用ツールの話です。アルバイトの id:tom__bo くんの成果です。

swiro - A switching route tool for AWS

EC2におけるRoute Tableベースのフェイルオーバツールです。アルバイトの id:taku_k くんに作ってもらいました。

サーバモニタリング向け時系列データベースの探究 / The study of time-series database for server monitoring // Speaker Deck

IOTS2016で招待講演で、Mackerelのための時系列データベースを求めてたどり着いた一つの結論の話です。

Varnishによる一貫性を考慮した積極的キャッシュ戦略実験 - でこてっくろぐ ねお

ISUCON6の予選を題材に、汎用的な手法でなるべく多くのアクセスをVarnishにキャッシュさせようとした試みです。

sabaviz Chefviz creates the dot files of recipes dependency-graph for graphviz.

これもアルバイトの id:tom__bo くんの趣味の成果です。はじめてみるサービスの依存関係の把握が難しかったので、依存関係を可視化するツールを作ってみたとのことです。

System Engineering

雑な LVS/TUN の解説図 - mura日記 (halfrack) LVSでTunnel方式のL3DSRを実現した様子の図解です。入社したときに、これがわかっていないとLVSオペレーションしてはいけないみたいなことを言われて勉強した記憶があります。

Linuxサーバにログインしたらいつもやっているオペレーション - ゆううきブログ よくあるLinuxコマンド集にみえますが、実際に入社してから使い続けたものを厳選しています。

ウェブアプリケーション開発に新言語を採用したときにインフラで考えたこと - ゆううきブログ ここ数年、はてなではアプリケーション開発言語としてScalaとGoが採用されているのですが、プログラムを書く以外の観点が見過ごされがちだったので課題についてまとめました。第3回関西IT系インフラ勉強会内容とだいたい同じです。

仮想化基盤Xenの性能評価 / Performance evaluation of virtualization platform Xen // Speaker Deck 第3回関西IT系インフラ勉強会での発表です。最近は1台に30近い仮想ホストが蠢くようになっているので、仮想化基盤の安定化が課題です。

nginxでproxy_hide_header, proxy_set_header, add_headerを書く時にはまりがちな罠 - でこてっくろぐ ねお nginxの設定は、上位のコンテキストから下位のコンテキストに設定を継承しようとするとハマりどころが増えるという話ですね。

最近AWSのENIの付け替え速度がチョッパヤになってる気がしたので測ってみた - でこてっくろぐ ねお id:dekokun という人はチョッパヤみたいな一昔前の俗語が好きなようです。これをデコ感と呼びます。

AWS EC2でのHTTP/2 or SPDY導入方法 - Hatena Developer Blog AWSでのHTTP/2 or SPDY運用の課題とPROXY protocol - Hatena Developer Blog

はてなでもHTTP/2の導入が進んでいます。ELBを使いつつ、HTTP/2を利用するのに癖があります。3部作といいつつ、3つ目はどうなったのでしょうか。(ALBがもうでてしまった)

PostgreSQLで異なるメジャーバージョン間のレプリケーション実験 - tom__bo’s Blog 第7回 PostgreSQLアンカンファレンス@東京に行ってきた - tom__bo’s Blog

PostgreSQLのオンラインバージョンアップ方法を調べてもらっていました。MySQLのように数珠つなぎレプリケーションをするわけにはいかないようです。自ら発表したいということで、第7回PostgreSQLアンカンファレンス@東京で発表してもらいました。

Googleが数千台もある10年前のLinuxディストリをライブアップグレードした話 - ゆううきブログ

CentOS5のEOLは来年3月で、ちょうどディストーションのアップグレードに興味がありました。Googleでさえ、かなり泥臭いことをやらないといけないことがわかりました。

はてなにおけるLinuxネットワークスタックパフォーマンス改善 / Linux network performance improvement at hatena // Speaker Deck

はてな・ペパボ技術大会の発表です。よくあるチューニングを除いて、ウェブサービスでLinuxネットワークスタックがボトルネックになるケースは多くはないのですが、ユーザをたくさん抱えているとカーネルレイヤのチューニングが必要になることがあります。

Mackerelにおける時系列データベースの性能改善 / Performance Improvement of TSDB in Mackerel // Speaker Deck

同じく技術大会の発表です。こちらは、時系列データベースGraphiteの性能改善事例です。パフォーマンスが低下したときに、カーネルレベルで分析し、PRをなげて問題解決しました。

計算量と僕とWeb開発 / computational complexity and I and Web // Speaker Deck

同じく技術大会でのゆるふわ?計算量の話です。競技プログラミングで鍛えた感覚でだいたい計算量がわかるとのことです。すごいですね。

負荷分散技術を選ぶときに考えること // Speaker Deck

同じく技術大会での発表です。ネットワークからミドルウェアのレイヤまで幅広く抑えられているのが特徴です。はてなではいろんなレイヤで負荷分散を実現しています。

仮想化基盤のリソース最適化 / Resource optimization on virtualization platform // Speaker Deck

同じく技術大会での発表です。仮想ホストを構築するときに、どこの物理サーバを選べば良いのかをがんばって探さないといけないという課題があり、数学的モデルに落とし込むことで最適な配置ができるというものです。現実には、かなり多くの制約条件があって、プログラマブルに値をとりにくいものもあるので、なかなか難しいですね。

はてなでの サービス信頼性向上のための 取り組み事例 // Speaker Deck

SRE tech talksでの発表です。 ちょうと社内でSRE輪読会をやっていたところ、声がかかったので良いタイミングでした。SREの視点を通して、最近のはてなのウェブオペレーションを俯瞰するとどうみえるかという内容になっています。

ISUCON予選突破を支えたオペレーション技術 - ゆううきブログ

Kyoto.なんか #2での発表内容です。ウェブオペレーションエンジニア視点で、ISUCONという競技を自分なりに捉え直したものです。

はてなのログ運用 これまでとこれから / Hatena Engineer Seminar #6 // Speaker Deck

Hatena Engineer Seminar #6 〜インフラ編〜の発表です。rsyslogからfluentdへの変遷など。参加された人に聞くと、リバースプロキシでcronでアクセスログ送信しているところ、意外とやっている人がいるということに驚きました。

はてなのサーバプロビジョニングについて / Hatena Engineer Seminar #6 // Speaker Deck

同じくセミナーでの発表です。Chefなどのconfigurationフェーズの話は世の中にたくさんでてますが、OSイメージの作成などbootstrapフェーズも含んだ話は意外と少ないのではでしょうか。

MySQL運用とらぶるすとーり〜^2 / MySQL-Troubleshooting-Story // Speaker Deck

同じくセミナーでの発表です。MySQL芸人こといちりんちゃんの磨きのかかった発表でした。テーブルの行数制限にあたった話とbinlog破損から救いを求めた話です。

はてなのサーバ/インフラを支える技術〜2016年新卒編〜 / OSC Tokyo 2016 Fall // Speaker Deck

OSC Tokyo 2016での新卒2人による発表です。新しい広告配信システムのインフラの話と、はてなのサーバ・ネットワークの基盤の紹介です。

セキュリティ会の取り組み - Hatena Developer Blog

セキュリティ会自体は、ウェブオペレーションエンジニアとは直接関係ありません。専門のセキュリティエンジニアがいるわけではないので、セキュリティ会が、情報を収集し、対応をまとめ周知するという役割を担っています。

MySQL-5.6のMRRにデッドロック回避の夢を見る - ichirin2501's diary

MySQLのロックの挙動を調査するために、gdbで解析してたりします。

フルCDNアーキテクチャ実験 / Minami Aoyama Night #1 // Speaker Deck

Minami Aoyama Night#1での発表です。はてなブログのHTTPキャッシュ戦略と、のちにやりたいと思っているフルCDN化についての発表です。

はてなのインフラ環境を自宅で再現する // Speaker Deck

YAPC::Hokkaido 2016での発表です。自宅で動いたから検証済みとかいって本番に投入していく新卒(詐欺)です。

はてなにおけるデータセンター内ネットワークの歴史と今後

DataCenter Networking Conference での発表です。はてなのこれまでのネットワークを振り返るような話になっています。いちWebサービス事業者が今もオンプレでネットワーク運用している例は、昨今では少ないんじゃないでしょうか。資料はそのうち公開されると思います。

10ms以下のレスポンスタイムを支える継続的負荷テスト - taketo957の日記

低レイテンシを求められる広告配信システムでやっている負荷テストCIの話です。負荷テストCIってよくあるアイデアのわりにはあまり見かけないですね。

LinuxのARPとL2スイッチのお話 - masayoshiの日記

LVSのDSRで非対称ルーティングしているときのネットワークのトラブルシューティングの話です。

輪読会

社内でSRE本*1の輪読会を開催し始めました。 世間で言われているエラーバジェットやToilの割合を一定以下に収める努力などが書かれているのはもちろんですが、SREというのは単に定量的アプローチのことだけを指すわけではないということがわかってきています。

その他

法学部生だけどはてなのインフラで4年間バイトした - naokibtn’s blog

長い間おつかれさまでした。

株式会社はてなに入社しました - masayoshiの日記 株式会社はてなに入社しました - taketo957の日記

今年はなんと新卒のWebオペレーションエンジニアが2人も入社しました。

リモートワークにおけるSlack Call活用と終業15分前の雑談 - Hatena Developer Blog

雑談に限らずコミュニケーションの機会を意識的に増やしはじめました。

2016年ウェブオペレーションエンジニアの新卒研修 - Hatena Developer Blog

新卒が2人もきたので、研修し始めました。

東京にいながら仕事のほとんどを京都のエンジニアと一緒にしている私のリモートワークの話 / Hatena Engineer Seminar #6 // Speaker Deck

セミナーでの発表です。Webオペレーションエンジニアは東京でも募集しています。

アプリケーションエンジニアからみたはてなのインフラの話 / Hatena Engineer Seminar #6 // Speaker Deck

セミナーでの発表です。id:KGA さんはWebオペレーションエンジニアではありませんが、アプリケーションエンジニアからみたWebオペレーションエンジニアの話をしてもらいました。

情報処理学会でウェブオペレーション技術について招待講演した話 - ゆううきブログ

なぜか研究者のコミュニティで技術者として講演しました。

ウェブオペレーションエンジニアになるまでの思い出 - ゆううきブログ

Hatena Engineer Seminar #7 での発表内容です。思い出に共感してもらい、Webオペレーションエンジニアに興味をもってもらうという趣旨でした。

サーバとわたし - Words fly away, the written letter remains.

id:tomomii さんは職種としてはエンジニアではありませんが、tomomiiさんらしい感性でとらえた技術の話がたのしいです。

あとがき

はてなのWebオペレーションエンジニアはすごいことをしているのに外へのアウトプットが全然ないなぁと思ったのが、僕がアルバイトにきた2012年のことでした。すごいことをしているのにもったいないと思って、ちまちまとブログを書いたり発表し続けてきたりしました。 今年から自分だけでなくチームメンバーにもアウトプットを促すようになり、アルバイト含めたすべてのWebオペレーションエンジニアがなんらかのアウトプットをした年になりました。

こうして1年俯瞰してみると、はてなのWebオペレーションエンジニアの特色が浮きぼりになります。 ネットワーク、Linux、仮想化、RDBMS、WebサーバといったWebのインフラを支える運用技術(System Engineering)については、自信をもって強いと言えます。しかし、Mackerel以外で、Software Engineeringにより自分たちで最適なシステムをつくっていくという点がまだまだ弱いのが課題だと思っています。

SREに代表されるように、インターネットのインフラの世界でSoftware Engineeringの重要性が高まっており、はてなでもSoftware Engineeringによりシステムの信頼性を高めたいと考えています。 はてなでは、インフラの領域でソフトウェアを書いてみたい、これまでWebアプリケーションエンジニアだったけどインフラの世界に興味があるといった方を募集しています。 もちろん、今のはてなの強みでもあるSystem Engineeringのスキルを生かしたいという方も大歓迎です。

新卒の採用募集もやっています!

*1:Betsy Beyer, Chris Jones, Jennifer Petoff, Niall Richard Murphy, "Site Reliability Engineering: How Google Runs Production Systems", O'Reilly Media, March 2016

はてな「Webオペレーションエンジニア座談会」を公開しました

本日、採用ページの新たなコンテンツとして「Webオペレーションエンジニア座談会」を公開しました。

10年続くサービスを、インフラ技術で支える――Webオペレーションエンジニア座談会 - 株式会社はてな

はてなのインフラチームからid:wtatsuruid:y_uukiid:dekokunid:taketo957の4人が参加し、入社のきっかけやはてなでの働き方、チームの将来像などについて語り合いました。「はてなのインフラチームってどんなふうに仕事をしているの?」という疑問にお答えします。

はてなでは京都・東京の両拠点で、Webオペレーションエンジニアの積極採用を行っています。皆さまのご応募をお待ちしています。

Webオペレーションエンジニア職 - 株式会社はてな

開発速度と品質のトレードオフの判断基準の合意

はてなエンジニアアドベントカレンダー2016

Webサービスの開発は、ユーザ/顧客へ価値を早く届けるため、競合より早くリリースするため、人的リソースを無駄使いしないためなど、とにかく素早く進めたいものですね。一方で、開発を急ぐあまり品質を犠牲にすればかえって価値が失われたり、技術的負債が溜まって長期的なコストが大幅に増大する可能性もあります。開発速度とプロダクト品質は基本的にはトレードオフの関係にあるのでしょう。

開発速度と品質のどちらを優先するかはプロダクトの性質や、チームもしくは会社の状況によって異なるとおもいます。この状況の認識がチームメンバー間でずれていると、チームのパフォーマンスを最大限に発揮できないばかりか、チーム内の関係悪化も招きかねません。エンジニアたちとプロダクトオーナーの間の対立のようなありがちな問題の原因の一つかもしれません。

そこで、開発速度と品質のトレードオフをどう判断すべきかの基準を明確にして、原則それに従うことをあらかじめチーム内で合意してみました。

この記事は、はてなエンジニアアドベントカレンダー2016の24日目で、担当はid:taraoです。昨日の担当はid:takuji31さんのAtomの自動補完プラグイン「autocomplete-plus」のPerl用Providerを書いている話でした。

Read more

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

はてなエンジニアアドベントカレンダー2016

こんにちは!はてなアプリケーションエンジニアの id:takuya-a です。

みなさんは、このような疑問をもったことはありませんか?

  • grep はどのように文字列を検索しているのか?
  • MeCab はどうやって辞書を高速にルックアップしているのか?
  • パーサやコンパイラを作りたいけど、何から始めればいいのか?

本稿では、「文字列アルゴリズムとはどんなものなのか?」「なぜ重要なのか?」「何を知っておくべきか?」「どうやって勉強すればいいのか?」といった疑問にお答えしていこうと思います。

文字列アルゴリズムの意外な応用や、モチベーションを保ちやすい勉強のしかた、文字列アルゴリズムを勉強するために行った社内での取り組み、実装するときのコツといったトピックについても触れています。

このエントリは、はてなエンジニアアドベントカレンダー2016の22日目の記事です。昨日は id:syou6162 さんによる はてな社内で行なっている機械学習勉強会について紹介します でした。

文字列アルゴリズムとは

文字列処理は、プログラミングにおいて日常的に使われるわりには、文字列アルゴリズムについてはあまり知られていないように思います。くわしい説明は後にして、ここでは文字列アルゴリズムの分野をごく簡単に紹介します。

もっとも基本的な文字列アルゴリズムは、部分文字列検索(パターンマッチ)でしょう。 複数のファイルから検索する場合はとくに全文検索と呼ばれます。 とくに grep などの文字列検索ツールへの応用が有名ですね。

その他にも、パターンの数が数百万以上になっても高速に検索するアルゴリズムや、いくつかの文字の違いを許容するあいまい検索などの複雑な検索にも対応できるアルゴリズムもあります。

さらに、音声認識やデータ圧縮、時系列パターンマイニングといった、単なる文字列検索にとどまらない応用があり、数々のアルゴリズムの分野のなかでも文字列アルゴリズムは特に重要であると考えています。

なぜ文字列アルゴリズムを学ぶのか

ここでは応用先を中心に、文字列アルゴリズムを学ぶことでできるようになることを紹介します。以下のように多様な応用があります。

  • 全文検索
    • 検索エンジンには様々な応用がある
    • 転置インデックスの辞書やあいまい検索など
  • パーサ・コンパイラ
    • オートマトンの理論を共通の基礎とする
    • 自分の DSL を作ったり、独自のパーサを書いたり
  • 自然言語処理
    • 自然言語処理は文字列を扱うことが多いので、文字列アルゴリズムの重要度は高い
    • 形態素解析などには直接応用されている
  • 機械学習
    • 文字列(単語など)を素性とする機械学習で応用可能
    • 精度や前処理のパフォーマンス向上が狙える
  • 音声認識
  • パターンマイニング
    • 時系列データ解析・ログ解析など
    • 類似パターンや繰り返しのパターンを発見する
  • データ圧縮
    • bzip2 などの圧縮アルゴリズムに応用されている(文字列アルゴリズムの一種である BW 変換を利用)

これら以外にも、基礎を知っていれば意外なアプリケーションに利用できることもあります。たとえば、ISUCON6 で出題されたことが記憶に新しいはてなキーワードのキーワードリンク作成(テキストのキーワード部分にリンクをつける処理)でも、後述するトライ木を利用することで高速に行うことができます。そのほか、テキスト中からn回以上現れるフレーズを高速に抽出する、などの応用もあります。

また、文字列アルゴリズムは、工夫すればバイナリにも適用することができます(「番兵とヌル文字」を参照)。つまり、アルゴリズムによっては、なんらかのデータの並び (sequence) でさえあれば適用できる可能性があります。あなたの発想次第で、意外なところが高速化できたり、アプリケーションをもっと大規模なデータに適用できるようになるかもしれません。

最初に知っておくべきこと

文字列アルゴリズムの世界は広大なので、そのすべてを一度に勉強するのは難しいと考えています。興味のある分野で関連領域をひとつずつ潰していくのがおすすめです。

基礎的な文字列アルゴリズムには、ざっと以下のようなものがあります。

  • 文字列のソート
  • 部分文字列検索(パターンマッチング)
  • 複数パターンマッチング・辞書データ構造
  • 正規表現マッチング
  • あいまい検索

まずは、具体的なアルゴリズムを勉強し始める前に、各アルゴリズムの特徴と使いどころをつかむところから始めましょう。それぞれに代表的なアルゴリズムを、後ほど特徴とともに簡単に説明します。また、思い立ったときにすぐ学習を始められるように、参考リンクなどのリソース集を併記しますので、興味が湧いたときにのぞいてみてください。

どうやって勉強するか

経験上、文字列アルゴリズムを勉強するモチベーションを保ち、理解していくうえで最も効果的だったのは、自分が作りたいものを実装してみる ことでした。

前職では全文検索エンジンを開発していたのですが、自分にとって一番のブラックボックスは形態素解析でした。形態素解析器の中身を知りたい!という興味から、Kuromoji という Java の形態素解析器のソースコードを読み始めたり、 NLP の資料や論文を読んでみたものの、「理解した!」と思うにはほど遠い状況でした。

そこで、自分が好きだった JavaScript で形態素解析器をゼロから書いてみようと思い立ち、ダブル配列(後述する、トライ木というデータ構造の一種)とビタビアルゴリズム(動的計画法の一種)による形態素解析器を実装しました。実装してみることで、処理のどこに時間がかかるのか、データはどのように保存されてどう読み出されるのかなど、形態素解析の動作が手に取るようにわかるようになりました(とはいえ、辞書のクセにはずっと翻弄され続けていますが…)。

目的とするアプリケーションの部品が組み上がっていくのは、とても楽しい経験でした。アルゴリズムだけを勉強しようとしていたとしたら、間違いなく挫折していたと思います。

ここで言いたかったのは、文字列アルゴリズムの教科書を開く前に、まず 作りたいものを探すことから始めるという勉強法もある 、ということです。 最初は簡単なアルゴリズムを応用したものでよいと思います。解きたい問題、作りたいアプリケーションによって、関連するアルゴリズム・分野を深掘りしていくと、教科書的に勉強するよりもはるかに深い理解が得られます(また、その副産物として新しい OSS ができることもあります)。

モチベーションを保つ上でもうひとつ重要なことは、「仲間を探す」ことです。ひとりで自分を高め続けるのはとても苦しいことですが、苦労や感動を共有できる人がひとりでもいれば、学習を継続できる確率は飛躍的に高まるでしょう。

社内勉強会の取り組みについて

「作りたいものを実装してみる」以外の、もうひとつの勉強法として、仲間を集めて勉強会を開催するという手があります。今回は、社内で実施している、文字列アルゴリズム勉強会の取り組みについて紹介します。

具体的には、カリフォルニア大学サンディエゴ校のオンライン講座 (MOOC) をみんなで受講しています。私は、文字列アルゴリズムのなかでもとくに接尾辞配列や、その関連アルゴリズムに苦手意識があったのですが、その勉強にちょうどいいオンライン講座をたまたま見つけました。それが Coursera で開講されている Algorithms on Strings です。社内で紹介したところ、幸い興味をもってくれた仲間を集めることができました。

機械学習の社内勉強会でも Coursera を活用していたこともあり、同じような形式で進めています。

  • 昼休みや夜に、講義ビデオをみんなで見る
  • わからないところは適宜ホワイトボードを使ったりして話し合う
  • 週末にプログラミング課題を実装する

この講座の一番いいところは、毎週プログラミング課題が出ることです。課題では、実装すべき関数の入力と出力が明確に決められており、本質的ではない部分はあらかじめ実装されている雛形が提供されています。これにより、 文字列アルゴリズムを実装するための心理的ハードルが極限まで下がっている状態 になっています。あとはやるだけです。

ひとつ残念な点は、無料で受講しているかぎり課題が採点されないことです!ただ、課題ができなくてずるずる遅れていく…といったことがないので、内容さえある程度理解していれば毎週気軽に参加できるというメリットもあります(もちろん実装したほうが理解は深まりますが)。

現在は(講座本来のペースからは遅れながらも)最終週までたどりつくことができています。なんとか年内には完走できそうです!

代表的な文字列アルゴリズム

ここでは、代表的なアルゴリズムについて、ひとこと解説と、参考になる学習リソースを示します。

最初は、この解説ではおそらく意味不明だと思いますので、興味が湧いたらぜひ参考リンクの記事や書籍を読んでみてください。

1. Brute Force による文字列マッチング

  • もっともシンプルな部分文字列検索アルゴリズム
  • 1文字ずつずらしながら部分文字列すべてとテキストの文字を比較する
  • 文字がマッチしなかったらテキストの次の位置をみる
  • Brute force algorithm

2. KMP による文字列マッチング

  • 文字位置をスキップすることで比較回数を減らす
  • 理論上は重要
  • 実用上は後述する BM 法、とくに Quick-Search (Sunday のアルゴリズム) が使われている
  • Algorithms on Strings の3週目で登場

3. BM (Boyer-Moore) による文字列マッチング

4. Bitap (Shift-And / Shift-Or) アルゴリズムによる文字列マッチング

5. Rabin-Karp (Rolling hash) による文字列マッチング

  • 工夫した多項式ハッシュ関数を用いることで、テキストの長さに対して線形時間で検索可能
  • 位置nからm文字の部分文字列のハッシュ値から、位置n+1(1つずらした)からm文字の部分文字列のハッシュ値を高速に( O(1) で)計算できる
  • 位置をずらしていった、すべて(|Text| 個)の部分文字列のハッシュ値を O(|Text|) で計算できる
  • 詳しくは蟻本ことプログラミングコンテストチャレンジブック 第2版「4-7 文字列を華麗に扱う」を参照

6. トライ木 (Trie) による複数パターンマッチング

7. 正規表現のマッチング

  • とても表現力の高いパターンマッチが可能
  • 有限オートマトン (FSA) の理論と関係が深い
  • 正規表現エンジンの実装は大きくわけると DFA 型と VM 型という2種類がある
    • DFA 型:正規表現を決定性有限オートマトン (DFA) に変換し、その上での状態遷移をシミュレートする
    • VM 型: 正規表現を仮想マシン (VM) 上のバイトコードに変換し、 VM 上でのバイトコード実行をシミュレートする
  • 正規表現エンジンをどう実装するかについては、正規表現技術入門を読むのがおすすめ

8. 接尾辞配列 (Suffix Array)

  • 検索対象のテキストを接尾辞配列というデータ構造(元テキストと同じ長さの配列)に変換する
  • 接尾辞配列を使うと、パターンに対して2分探索で検索できるようになる
    • 大きなテキストに対しても高速
    • http://www.slideshare.net/nobu_k/suffix-arraysolr
    • 単純な実装では O(|Pattern| log |Text|)
    • LCP (Longest Common Prefix) 配列をあらかじめ計算して持っておくことで O(|Pattern| + log |Text|) になる
    • LCP 配列の計算については接尾辞木の項目を参照
  • 線形オーダー O(|Text|) で接尾辞配列を構築するアルゴリズムがある

9. 接尾辞木 (Suffix Tree)

10. BW 変換 (Burrows-Wheeler Transform)

  • bzip2 の前処理として利用されている
  • BW 変換後の文字列 (BWT) はテキストと同じ長さの文字列になる
    • このとき、同じ文字が並びやすくなる、つまり元の文字列にくらべて圧縮が効きやすくなる
    • (英語の場合) nd の前には a が来やすい、みたいな性質を使っている(and という単語が頻出するので)
  • BWT から元のテキストが復元できる(逆変換が可能)
    • First-Last Property という性質を利用した LF-mapping を使う
    • Algorithms on Strings の2週目のビデオがわかりやすい
  • SA-IS を使うことで O(|Text|) で計算可能

11. FM-index

  • 圧縮インデックス
  • 通常の転置インデックスに比べて、動的な更新は難しい
  • 高速文字列解析の世界 7.5.2 に FM-index を使った検索についての解説がある

文字列アルゴリズムを実装するときのコツ

実用的なアプリケーションやライブラリを作るのは、試しに実装するよりもはるかに大変です。ここでは、実装のコツをいくつか紹介します。

テストを書く

基本的なことですが、テストを書きましょう。一般的にアルゴリズム・データ構造の実装は、バグが入り込みやすく、潰すのは難しいです。とくに境界条件のテストは念入りに行うようにしましょう。

文字列アルゴリズムは基本的には関数単位で実装でき、入力と出力が明確です。そのため、複雑なアプリケーションに比べてテストが書きやすいといえます。テストがしっかりあって、試行錯誤しやすい状態になっていると、パフォーマンスチューニングも格段にやりやすくなります。

簡単なものから実装する

これも基本的なことですが、まず思いつく最も簡単な実装を行い、そのあと効率的なコード・複雑なアルゴリズムを書きます。

文字列検索を考えたとき、まず最初に実装すべきは、力まかせ (Brute Force) による部分文字列検索です。複雑なアルゴリズムに進む前に、文字列アルゴリズムのもっとも基本的な道具である、以下の3つを使いこなせるようにしておきます。

  • 文字列から文字へのインデックスアクセス (charAt)
  • 文字列の長さ (length)
  • 文字の比較

「簡単なものから実装する」というルールは、他のアルゴリズムを実装するときにも使えます。「早すぎる最適化を避ける」というのは、ソフトウェア開発におけるベストプラクティスのひとつでもありますよね(なかなか実践できないことでも有名ですが)。

また、他の文字列検索アルゴリズムを実装するときのベースラインにもなります。「推測するな、計測せよ」という格言もありますが、より高度なアルゴリズムを実装するとき、ベースラインからどれくらい速くなったかは重要です。また、速いアルゴリズムを実装したはずなのにそんなに速くなってない、といったケースでバグを早期に発見できることがあります。

マルチバイト文字の扱い

  • 可変長の符号化方式を使っている場合は、文字単位でのインデックスアクセスが困難
  • Unicode であれば UTF-16/UTF-8 が主流
    • UTF-32 なら困難はない(固定長なので)
  • UTF-16/UTF-8 は可変長の符号体系
    • UTF-16: サロゲートペア
    • UTF-8: 1文字のサイズが可変(1バイト〜4バイト)
  • 検索結果として得られる位置は文字の位置ではない
    • UTF-16: サロゲートペアがない場合は文字の位置と一致
    • UTF-8: 位置はバイト配列の何バイト目かを表すにすぎない
  • UTF-16/UTF-8 であれば、文字の内部でヒットすることを避けられる
    • UTF-8: 文字の1バイト目かそうでないかが判定できる符号体系(ビット演算で判定可能)
    • UTF-16: 2バイトのコードポイントで判定できる符号体系
  • Unicode のサロゲートペアとは何か - ひだまりソケットは壊れない

番兵とヌル文字

アルゴリズムによっては番兵(何かしらの区切りや終端を表現する文字)が必要なものがあります。このとき、文字列中のどんな文字でもない文字を番兵として使うことになります。ヌル文字 \0 を使うことが多いようです。

しかし、バイナリに対して文字列アルゴリズムを適用したい場合、これが問題になります。バイナリを文字列として捉え、その中から検索したいとします。すると、バイナリには \0 が現れないことを保証できないため、番兵が用をなさなくなってしまいます。

つまり、バイナリも扱いたい場合は、番兵を陽に使わないような工夫が必要なのですが、アルゴリズムによって対処方法は異なりますし、実装難易度は跳ね上がります。頑張りましょう。

さらに学ぶために

まとめ

  • アルゴリズムを勉強するには、なにより実装してみることが大事
    • grep などの文字列検索アルゴリズムが具体的にイメージできるようになる
    • アルゴリズムをより深く理解できる
    • モチベーションを保ちやすい
  • 社内では文字列アルゴリズムの勉強にも Coursera を活用しています
    • わかりやすい講義ビデオ、雛形を用意してくれている課題
    • モチベーションまではコントロールしてくれない
    • 仲間を集めるなどの工夫もあるとよいですね
  • 抑えておくべき文字列アルゴリズムを簡単に紹介しました
    • 他にもおすすめのアルゴリズムがあれば教えてください!

はてなでは文字列が好きなエンジニアを募集しています。

hatenacorp.jp

明日のアドベントカレンダーは id:takuji31 さんです!