豪鬼メモ

一瞬千撃

EPUBリーダ用のEPUB英和辞書を作ろう

EPUB対応の電子書籍リーダーで共通して使えるEPUBの電子辞書データを作ろうと思いたち、例のWiktionaryとWordNetの統合辞書データを変換して実際に作ってみた。また、一連の英和辞書関連のプロジェクトページも作った。

英和辞書の曖昧一致検索と類語検索

オープンなデータで英和辞書と和英辞書を構築して検索する連載の5回目である。今回は、曖昧一致検索も含めた複雑なパターン一致検索を実装し、さらに類語検索も実装する。曖昧一致検索と類語検索は、辞書の利便性を飛躍的に高めてくれる。いつものデモサイト…

WictionaryとWordNetから英和辞書を作ろう

英和辞書・和英辞書として使える辞書検索システムを作る連載の4回目である。今回はWictionaryから辞書データを抽出して、WordNetとも併合して、本物の英和辞書として使えるシステムを構築した。今回もデモサイトを作ったので、お試しいただきたい。凝った機…

WordNetを使った辞書検索システムのプロトタイプ

DBMで単語辞書を作る連載の3回目だ。今回はデモを実装した。仕様を単純化したプロトタイプであり、基本的な機能の説明をするのに丁度よいはずだ。それにもかかわらず、普通に実用できるものに仕上がっている。

Wikipediaの共起語を使ってシソーラス検索をしよう

前回、Wikipediaの記事を解析して、単語の共起語のデータベースを作った。今回は、共起語データベースを解析して類語を推定する。すなわち、共起語データベースをシソーラスとみなして、関連語の検索を行う。

Wikipediaを解析して共起語抽出をしよう

DBMで単語辞書を作る連載の2回目だ。今回作る辞書検索システムの看板機能は、類語検索である。そして、類語を自動的に推定するための一手法として、共起語を使う方法がある。ここでは、Wikipediaをコーパスとして、共起語を抽出する。

DBMを使った検索エンジンの作り方

キーワード検索システムとか全文検索システムとか検索エンジンとか呼ばれる仕組みの肝は転置索引とか転置インデックスとか呼ばれるデータベースである。それは、検索語をキーとして、その検索語に該当する文書のIDのリストを値とする連想配列に他ならない。…

reallocによる配列拡張の償却時間計算量

reallocを使ってメモリアロケーションのサイズを少しずつ伸ばしていく際に、償却時間計算量はO(N)になるだろうか、それともO(N^2)だろうか。結論としては、普通にやるとO(N^2)になる。ただし、セオリー通りにアプリケーション側で工夫するとO(N)にできる。性…

DBMで単語辞書を作ろう

データベースマネージャTkrzwを無事にリリースしたはよいが、ドッグフードは自分で食わないといけない。DBMを作るとまず最初にやりたくなるのが、それを使った単語辞書を作ることである。仕事柄、英和辞書と和英辞書はよく使うのだが、自分で作ったものを毎…

レンタルVPSにUbuntu 20をインストールする手順

レンタルのVPSで自分のLinuxサーバを運用しているわけだが、その再インストールと再設定を行った。新しいドメイン名を取得して、新しいOSを入れて、Webサーバを立てて、開発環境を構築する。これはその手順の自分用のメモだが、似たようなことをしたい人には…

データベースライブラリTkrzwの初版リリース

データベースライブラリであるTkrzwの初版をリリースした。Kyoto Cabinetの正式な後継製品である。本家のサイトはここである。設計目標の通り、高速かつ堅牢で多目的に使える実装になったと思っている。私の下手な英文を読ませるのも忍びないので、ここに概…

LRU削除キャッシュDBM

キーと値の連想配列であるDBMのインターフェイスでLRUレコード削除機能付きのキャッシュ機構を実装してみた話。

開発作業と椅子と尻

頭脳労働者諸氏が家に籠もって仕事をするようになって早数ヶ月、その末席に連なる私も、自室の椅子に座って一日中作業をするのが日常になった。環境の変化によって多かれ少なかれ体調を崩す人もいることだろう。腰痛とか肩こりとか頭痛とか鬱とか。私の場合…

DBMのローカルシャーディング

データベースの文脈において、シャーディングとは普通はデータベースを行で水平分割して複数の計算機に割り当てることを意味する。今回は敢えてそれをローカルで行う機能について考えてみたい。つまり、単一の計算機上でデータベースファイルを複数に分けて…

DBMのC++/Java/Python/Rubyインターフェイス

この週末の頑張りで、Tkrzwの実装がほぼ全て完了した。権利関係の処理が済むまでにもうちょいかかりそうなので、先に各種プログラミング言語でのAPIについて語りたい。C++、Java、Python、Rubyのインターフェイスを比較してみると面白い。

ラテン文字のマッチング用正規化

小ネタなのだが、ラテン文字のマッチング用の正規化処理を自前で書くにはどうすれば最も簡単なのか考えてみた。

DBMの設計と実装 その21 実装作業に向けて

長きに渡った集中連載もこれでひとまずは終了である。過去ログはこちらを見てね。最後に実装作業の計画についてまとめておこう。

DBMの設計と実装 その20 セカンダリインデックス

DBMをRDBMS風に使うためにセカンダリインデックスを使いたくなる場合もあるかもしれない。その設計と実装について考えてみたい。

DBMの設計と実装 その19 バックアップ

DBMでサービスを提供している最中に、データベースファイルのバックアップを取りたくなることがあるだろう。当然、サービスのダウンタイムにならないように、データベースにアクセスする他のスレッドはブロックしないで行いたい。それにはどうするか。

DBMの設計と実装 その18 アトミックなレコード処理

私が設計したDBMに特徴的な機能である、アトミックなレコード処理について詳しく紹介したい。以前誰かがデータベースのクンフーであると言ってくれた面白い機能だ。

DBMの設計と実装 その17 ゾーンI/O

ファイルI/Oの実装として、ファイルの内容に同期したメモリ上の領域にアクセスするメモリマップI/Oを利用する際のインターフェイスについて考察する。

DBMの設計と実装 その16 オンメモリデータベース

DBMのインターフェイスでオンメモリのストレージを実現できる。その設計と実装について考えてみよう。

DBMの設計と実装 その15 スキップデータベースの検索

スキップデータベースを検索するアルゴリズムの要点について考えてみる。メモリ確保の戦略が重要になってくる。

DBMの設計と実装 その14 スキップデータベースの書式

ソート済みのレコードの連結リストにスキップリストを付与したものがスキップデータベースである。その具体的な書式についてここで完全に定義する。

DBMの設計と実装 その13 スキップリストの構造

ハッシュデータベースとツリーデータベースの設計については一段落したので、次にスキップリストデータベースの設計に移る。まずはスキップリストの概要についてまとめてみよう。

DBMの設計と実装 その12 ツリーデータベースの実装

ツリーデータベースを実装するにあたり、具体的にどういうデータ構造を使うかを検討する。並列化についてもここで検討する。

DBMの設計と実装 その11 ツリーデータベースの書式

ハッシュデータベースを基盤に構築したB+木のデータベースを、以後、ツリーデータベースと呼ぶ。データベース全体のメタデータとして何を持つべきか、B+木の各ノードはどのようなデータを持つか、またどのようにシリアライズするか、ここで完全に詰めて定義…

DBMの設計と実装 その10 LRUキャッシュ

B+木をファイル上で実現するにあたり、個々のノードのデータをシリアライズしてハッシュテーブルのDBMに格納するということを前回述べた。そして、個々のノードにアクセスする度にハッシュDBMの読み書きをすると遅すぎるので、キャッシュ機構が求められる。…

DBMの設計と実装 その9 B+木の構造

B+木を使ったデータベースの設計をしよう。これを使うと、レコードの順序に基づいた検索ができる。範囲検索とか、前方一致検索ができる。その基本的な構造について考察する。

DBMの設計と実装 その8 ファイルクラス毎の性能

前回設計した4つのファイル具象クラスを実装し、その性能を測ってみた。