Precaution
MOXBOX は日々のプログラミング経験や学習で習得した知識の理解を深めるために自分の理解の範囲で言語化し、必要になったときにいつでも思い出せるようにした上で安全に忘れて次の興味のための余力を脳に作ることを目的としている (従っていったん終えたことや周辺知識のことの方が多い)。基本的にノートであるため、時に数式の解法であったり実装アルゴリズムであったり、読書から要点抜粋した箇条書きであったり単なるコードのスニペットであったりと体裁はさまざまである。
このよう背景から、理解が及んでない部分には定義の不備、間違いなどが含まれる可能性がある。自分の理解と連動することから必ずしも学術的、時事的に正しい情報を載せていることを保証 (目的と) していない。
MOXBOX は 2017年9月下旬から書き始めた。サイトの Web サーバは Finagle をベースに実装した非同期 I/O サーバである。
Notation
特に明記しない限り \(\log\) の底は \(e\) とする。
最近の更新
\(\def\vector#1{\boldsymbol{#1}}\)
Log-Structured Merge Tree (LSMT)
LSM ツリー (log-structured merge tree) またはログ構造マージツリーはデータベースのようなストレージエンジンにおいて検索性能を維持しながら高い書き込み性能を達成することを主な目的として使用されるデータ構造の一種である。従来の B-Tree や B+Tree とは異なり、データの書き込みがディスクへのシーケンシャルな書き込みとなるように最適化されていることで、ランダムな書き込みの発生する構造より書き込み性能を向上させている。…
B-Tree
B-Tree または B 木は自己平衡型の多分木データ構造である。各ノードがソート済みの複数のキーと子ノードへの参照を持つことで、二分木より高さの低いツリー構造を形成することができる。このため検索や挿入、削除操作の効率が良く、特にディスクや SSD のようなストレージドライブに対する I/O を最適化するように設計できることから、大量のデータを効率的に管理するようなデータベースやファイルシステムなどで広く使用されている。…
木構造
木構造 (tree structure) はデータを階層的に表現するためのデータ構造である。ノード (頂点) とエッジ (辺) で構成されるグラフ構造の一種だが、閉路を持たない DAG である。
論文翻訳: An Introduction to Bε-trees and Write-Optimization
B-Tree と似た構造を持ち、更新と挿入で高い性能を持つ Bε-Tree に関する 2015 年の記事。
論文翻訳: Lower Bounds for External Memory Dictionaries
検索操作においては従来の B-Tree の定数オーダーの性能を維持しながら、更新操作のスループットを大幅に改善する Bε-Tree についての 2003 年の論文。
論文翻訳: Computing Extremely Accurate Quantiles Using \(t\)-Digests
大規模データセットから \(k\) 番目に小さい要素の近似値を効率的に見つけるためのアルゴリズム \(t\)-digest についての 2019 年の論文。
分位数
分位数 (quantile) またはクォンタイルはデータや確率の分布を一定の割合で区切るための値を指す。例えばデータを昇順に並べたとき、その累積割合が特定の値 (20%, 50%, 75% など) となる点を示すことで、データのばらつきや中心傾向、偏りなどを把握しやすくするための指標として使用される。…
論文翻訳: Sampling From a Moving Window Over Streaming Data
データストリームから得られる最近の \(n\) 個のデータからランダムサンプリングを行うために移動ウィンドウを使用した手法を解説する 2002 年の論文。1 つの「現在選択されているサンプル」と複数の「選択されているサンプルまたはその後継者がウィンドウを外れたときにサンプルとして選択される後継者」をチェーン状に保持することで、サイズ \(n\) の移動ウィンドウの中で常に 1 つの要素をサンプリングする。…
TRANSCRIPT: Various Techniques Used in Connection With Random Digits
A 1951 paper by John von Neumann discussing techniques for generating random numbers, dealing with pseudo-random number generation for Monte Carlo methods and its limitations.
論文翻訳: Ranking and unranking permutations in linear time
順列を識別する一意な整数を計算する「ランク」と、順列のランクに基づいて並びを生成する「アンランク」を効率的に行うアルゴリズムを提案する 2001 年の論文。従来の方法では \(O(n \log n)\) 時間がかかることが多いが、この論文で紹介されている手法では事前計算された階乗を利用して \(O(n)\) の線形時間実行できるようにしている。…
順列と置換
順列 (permutation) には次の 2 つの意味がある。複数の要素を直線的な順序で配置した状態 \(n\) 個の異なる要素からなる集合 \(A=\{a_0,a_1,\ldots,a_{n-1}\}\) は \(n!\) 通りの順列を構成することができる。例えば 3 個の要素からなる集合 \(\{a,b,c\}\) は \((a,b,c)\), \((a,c,b)\), \((b,a,c)\), \((b,c,a)\), \((c,a,b)\), \((c,b,a)\) の \(3!=6\) 通りの順列を生成できる。…
HyperLogLog
HyperLogLog は多重集合 (multiset) における異なりの数問題 (distinct-count problem) を概算するための確率的アルゴリズム。つまり同じ値が複数存在するデータセットから値の種類の数を概算する。異なりの数 (distinct count) とは SQL で COUNT(DISTINCT item) に相当する数であり、例えば集合 \(\{T,\) \(A,\) \(A,\) \(C,\) \(G,\) \(C,\) \(T,\) \(A\}\) の異なりの数は 4 である。…
論文翻訳: Hopscotch Hashing
既知のハッシュテーブルアルゴリズムより逐次/並行の両面でパフォーマンスに優れている Hopscotch ハッシュ法に関する 2008 年の論文 (ドラフト)。
論文翻訳: HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm
大規模データセットから要素のカーディナリティを推定するアルゴリズムである HyperLogLog に関する 2007 年の論文。HyperLogLog におけるカーディナリティとは distinct つまり「異なりの数」であり、集合論の文脈において「濃度」を意味するカーディナリティとは異なる点に注意。…
Boyer-Moore 過半数票アルゴリズム
Boyer-Moore 過半数票アルゴリズム (Boyer-Moore majority vote algorithm) は多重集合から過半数を占める要素 (\(N/2\) 個より多い要素) を見つけるためのストリーミングアルゴリズムである。(1) において選挙で投票された票の過半数を獲得した候補者を特定するアルゴリズムを例に紹介された。…
Count-Min スケッチ
Count-Min スケッチ (count-min sketch) (1) は大規模データセットにおいて頻度や重み付け合計を効率的に推定するための確率的データ構造である。膨大な数の要素を複数のハッシュ関数を用いて異なるカウンターにマッピングし、その最小値を参照することで頻度を推定する。…
論文翻訳: Don't Thrash: How to Cache your Hash on Flash
Quotient フィルターをカスケード上に配置してフラッシュデバイスへ対応した、近似メンバーシップクエリーのための確率的データ構造である Cascade フィルターに関する 2012 年の論文。
Quotient フィルター
Quotient フィルター (3) または商フィルターは大規模データセットに対する近似メンバーシップクエリー (AMQ; approximately membership query) を行うための確率的データ構造である。Bloom フィルターと似ているが空間とキャッシュをより効率的に利用できる構造を持つ上、テーブルサイズの変更や要素の削除をサポートすることができる。…
コンシステントハッシュ法
コンシステントハッシュ法 (consistent hashing) は分散システムにおいて処理やデータを均等に分散させるためのハッシュ技術である。Chord のような分散ハッシュテーブルにおけるオブジェクトロケーションのアルゴリズムとして使用されている。
ハッシュテーブル
ハッシュテーブル (hashtable) はさまざまなデータ型のキーをハッシュ化 (hashing) して効率的に管理し検索するためのデータ構造である。一般にキー \(x\) と関連する任意の値 \(y\) (サテライトデータ) を保持して \(y\) を効率的に検索するために用いられる。…
文字列マッチング
文字列マッチングは、テキストデータに含まれる特定の部分文字列 (パターン) を効率的に検索する技術である。大きな文書や巨大なデータベースで特定の単語やフレーズを見つけ出すために使用される。
Okapi BM25
Okapi BM25 は情報検索における文書のランク付けアルゴリズムの一つである。クエリーに対する文書の関連性を評価するために使用される。BM25 は TF-IDF の発展系として、特に文書の長さや単語の頻度に基づいて関連性スコアを調整するために設計されている。
固有値
正方行列 \(A\) について、\(Ax=\lambda x\) を満たす値 \(\lambda\) とベクトル \(x\) をそれぞれ \(A\) の固有値 (eigenvalues)、固有ベクトル (eigenvectors) と呼ぶ。
全文検索
全文検索 (full-text search) はテキストデータベースや文書集合として存在する構造化されていないテキストから特定の単語やフレーズを検索し、その出現位置や関連する文書を取得するための検索技術である。単純なキーワード検索と異なり、ランキング付けや表記揺れを考慮した検索によってよりユーザの目的に近い検索結果を提供する。…
論文翻訳: The Log-Structured Merge-Tree (LSM-Tree)
メモリ内のデータを定期的にストレージ上の大規模構造にマージすることで高い書き込みスループットと効率的なクエリー処理を実現するデータ構造である LSM-Tree に関する 1996 年の論文。
編集距離
編集距離 (edit distance) は 2 つの文字列間で一方の文字列を他方の文字列と一致させるために必要な最小の操作回数である。これは 2 つの文字列が互いにどれだけ異なるかを定量化している。文字列の類似性を評価するために自然言語処理の分野で広く使用されている。
Apache Lucene
Apache Lucene は高性能な全文検索とテキスト解析のためのオープンソースライブラリ。1999 年に Doug Cutting によって最初に開発され、その後 Apache Software Foundation のプロジェクトとして継続的に開発されている。Lucene は Java で書かれており、強力な検索機能はさまざまな規模のアプリケーションに柔軟に対応できる設計となっている。…
論文翻訳: FileDAG: A Multi-Version Decentralized Storage Network Built on DAG-based Blockchain
Kindle Paperwhite: KIOSK 端末化
Kindle Paperwhite: Jailbreak & SSH 接続
Amazon Kindle の Jailbreak はその本体がリリースされた当初からコミュニティによって活発に行われてきた。初期の手法はメーリングリストを通じて個々のユーザの作業によって貢献されてきた。しかしその積み重ねによって現在では情報が散在し、情報も口語の英語で書かれていて理解しにくい状況となっている。…
Kindle Paperwhite
論文翻訳: Cuckoo hashing
衝突時に他の位置へ要素を「追い出す」ことで高速な検索、挿入、削除が可能なハッシュテーブルの一種である Cuckoo Hashing に関する 2014 年の論文。
論文翻訳: Cuckoo Filter: Practically Better Than Bloom
要素が集合に含まれているかを効率的に判断するための確率的データ構造である Bloom フィルターの変種で、削除操作において Bloom フィルターより高い性能を示す Cuckoo フィルターに関する 2014 年の論文。Cuckoo ハッシュテーブルに基づいている。要素を格納する 2 つの位置を決めるのに部分キー Cuckoo ハッシングを導入したことで、元の要素を参照しなくても位置を移動できるようにしている。…
論文翻訳: A Tree Clock Data Structure for Causal Orderings in Concurrent Executions
因果一貫性において、Version Vector の因果履歴をベクトルからツリー構造にすることで処理の計算量をレプリカ数に対する線形から劣線形に改善するという 2022 年の論文。
論文翻訳: GossipSub: A Secure PubSub Protocol for Unstructured, Decentralised P2P Overlays
非構造化分散型 P2P オーバーレイで使用される安全な pub/sub プロトコルである gosshipsub について説明する 2019 年の論文。
論文翻訳: Merkle-CRDTs: Merkle-DAGs meet CRDTs
分散システムにおけるデータの同期を効率的に行う、Merkle-DAG と CRDT を組み合わせたデータ構造である Merkle-CRDTs に関する 2020 年の論文。
企業行動の理論
企業は市場経済における主要な経済主体の一つである。企業の行動は市場の価格や生産量などの経済変数に影響を与え、市場の機能や効率性に大きな影響を及ぼす。その動機は利益最大化であり、生産、価格設定、競争戦略などのさまざまな活動を通じてその目標を実現しようとする。本章では、企業の行動に焦点を当て、企業の意思決定が市場経済に及ぼす影響を考える。…
消費者行動の理論
ミクロ経済学は個々の主体が自己利益を最大化する合理的な行動をとるという一貫した前提に基づいて経済現象を説明する。経済活動の善し悪しは消費者一人一人の利益や損失に即して民主的に判断される。経済行動を誘因やインセンティブの観点から理解し、消費者の合理的行動がどのように現われるかを理解することが重要である。…
ナッシュ均衡
ナッシュ均衡 (Nash equilibrium) は各プレーヤーの戦略が互いに最適反応となっている状態である。つまり、集団の中で 1 人が戦略を変えたとしても本人の利得が増えない状況がすべてのプレーヤーに対して成り立っている状態である。
ゲーム理論
ゲーム理論 (game theory) は、複数の参加者 (プレイヤー) が互いに影響し合う状況でその戦略や意思決定を数学的にモデル化するための数学的な枠組みである。経済学、政治学、生物学、コンピュータ科学などの様々な分野で応用されている。
マルチエージェントシステム
マルチエージェントシステム (MAS; multi-agent system) は、複数の独立したエージェントが相互作用して目的を達成するためのシステムである。各エージェントは独自の目標や知識、能力を持ち、他のエージェントと協調したり競合しながら共通の目的を達成しようとする。マルチエージェントシステムは分散システムの一種である。…
モジュール性
認証と認可
Signal プロトコル
鍵導出アルゴリズム
鍵導出 (key derivation) は 1 つの秘密から複数の秘密を導出する手法である。より具体的には、ある鍵素体 (key material) から暗号論的強度を持つ 1 つ以上の秘密鍵を決定論的に導出するために用いられる。このような鍵導出を行うための関数を鍵導出関数 (key derivation function; KDF) と呼ぶ。…
RFC翻訳: HMAC-based Extract-and-Expand Key Derivation Function (HKDF)
ある秘密鍵に基づいて複数の鍵を生成するスキームを規定している RFC 5869 についての仕様文書。
JSON Web Token
Rust: RISC-V ビルド
仕様翻訳: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions - 転置に基づくハッシュ関数と拡張可能出力関数
暗号論的ハッシュ関数である SHA-3、および可変長出力が可能な SHAKE に関する 2015 年の NIST 仕様。
O'Reilly Japan - ソフトウェアアーキテクチャの基礎
ソフトウェアデザイン
TRANSCRIPT: A Fast Algorithm for Finding Dominators in a Flowgraph
A 1979 paper on dominator tree. A transcription of an old PDF for the purpose of reading it in machine translation.
word2vec
分散表現 (distributed representation) とは単語の意味を数値化してベクトル空間に表すことである。単語をベクトル空間に埋め込むことから単語埋め込み (word embedding) とも呼ばれる。一般に分散表現によって一つの単語は数十～数百次元のベクトルに変換される。…
論文翻訳: Efficient Estimation of Word Representations in Vector Space
3 層のニューラルネットワークを使用して単語の分散表現 (単語埋め込み) を生成するアルゴリズム Word2vec に関する 2013 年の論文。
CometBFT: データ構造
VSCode: 拡張機能開発
この記事では Visual Studio Code (vscode) の拡張機能の作成方法について説明する。拡張機能は vscode の機能を拡張するための小さなプログラムで、vscode の拡張機能エディタを使用して JavaScript または TypeScript で記述することができる。…
論文翻訳: Graph Drawing by Force–Directed Placement
Force-Directed Placement を用いてノード間の引力と反発力を調整してグラフ構造を 2 次元上に均等に配置する手法を提案している 1991 年の論文。Fruchterman-Reingold アルゴリズムとも呼ばれる。
CometBFT: ABCI
ABCI (application blockchain interface) は CometBFT コアの各コンポーネント (コンセンサス層) とブロックチェーンアプリケーションの実装 (アプリケーション層) が通信するためのインターフェース仕様である。ブロックチェーンアプリケーション開発者が CometBFT と連携するための標準的なプロトコルを定義している。…
CometBFT: P2P ネットワーク
P2P ネットワーク機能は (例えばコンセンサスアルゴリズムのように) CometBFT ノードが協調しながら進行する必要のある処理のためのフレームワークである。基本はアクターモデルに似た設計であり、ノード間のメッセージングから TCP のような下層の通信レイヤーの詳細を隠蔽し、メッセージの配信とそれを処理するリアクター (サービス) という概念に抽象化する。…
仕様翻訳: The RISC-V Instruction Set Manual Volume II: Privileged Architecture
RISC-V 特権 ISA に関する 2021 年の仕様書。
仕様翻訳: The RISC-V Instruction Set Manual Volume I: Unprivileged ISA
RISC-V 非特権 ISA に関する 2019 年の仕様書。
CometBFT: Mempool
mempool (メモリプール, メムプール) は未確定のトランザクション (unconfirmed transaction) を他のノードと共有し、提案ブロックの生成が行われるまで一時的に保存することを目的とした CometBFT の機構である。
CometBFT: コンセンサス
分散システムにおけるコンセンサスとは、分散ネットワーク上のすべての正常なノード間で合意を形成して共通の状態を確立するためのメカニズムである。よりブロックチェーン向けの表現では、コンセンサスに参加しているノードが「提案されたブロックを受理 (または拒否)」という共通の結論に到達するためのメカニズムを意味する。…
WebAssembly
WebAssembly または WASM はスタックベースの仮想マシン用バイナリ命令フォーマットである。バイナリを変更せずに様々な OS とアーキテクチャで実行できるように移植性の高い設計が行われている。WebAssembly は C++ や Rust、Go などの高レベル言語のコンパイルターゲットとして生成される。…
CometBFT 構造解説
CometBFT は強い一貫性を持つ分散システムを構築するためのソフトウェアおよびその SDK (software development kit)。プライベート/コンソーシアムブロックチェーン用途に特化している。同じ名前の CometBFT または旧名の Tendermint-BFT と呼ばれる BFT (Byzantine fault tolerance; ビザンチン障害耐性) 特性を持つコンセンサスアルゴリズムを実装し、ステートマシン・レプリケーションによるトランザクション直列化でブロックチェーンのブロックを生成することを目的としている。…
Rust: WebAssembly プログラミング
WebAssembly は可搬性の高い仮想マシン用バイナリ命令フォーマットです。Rust はターゲットバイナリに WebAssembly を選択することができます。
集合論
集合論は数学の基礎的な分野であり、数学的対象を扱う上での基本的な概念や枠組みを提供する。これは集合や要素の集まりを厳密に定義し、それらの性質や関係を明確にすることでそれらを形式的に表現したり操作を行うことができる。
符号理論
Base64 エンコーディング
Base64 エンコーディングは任意の長さを持つバイナリデータを ASCII テキストに変換するための符号化アルゴリズム。
誤り検出訂正
誤り検出訂正 (error detection and correction) はデータの伝送やデータ保存時におけるエラー (誤り) の検出と訂正を行うための手法。データは、伝送やストレージで生じる物理的なノイズや機器の不具合によって情報の欠損が生じ正確性を損なう可能性があるが、誤り検出訂正によってそれらのエラーを検出し訂正することで正確性と信頼性を向上させることができる。…
Erasure コーディング
Erasure コード (erasure code; 末梢符号) はビットの喪失に対する誤り訂正符号である。誤り検出訂正がビットエラーの検出や訂正を対象としていたのに対して、Erasure コードは喪失したデータブロックを他のデータブロックとパリティブロックから復元できることから、高い信頼性が求められる分散ストレージシステムなどで使用されている。…
Blockchain: レイヤー 2
秘匿共通集合
秘匿共通集合 (PSI; private set intersection) は 2 つパーティ \(P_a\) と \(P_b\) がそれぞれで保持しているデータ集合 \(A\), \(B\) の共通集合 (交差) \(A \cap B\) を特定できる暗号技術。共通集合に含まれない要素の情報は相手に一切明かされないことから二者間のデータプライバシー保護が重要なケースにおいて有用な暗号技術である。…
TRANSCRIBE: Judgement under Uncertainty: Heuristics and Biases
Very prominent 1974 paper on Heuristics and Bias. A transcription of an old PDF for the purpose of reading it in machine translation.
TRANSCRIBE: Non-Interactive Oblivious Transfer
A 1990 paper on non-interactive oblivious transfer. A transcription of an old PDF for the purpose of reading it in machine translation.
紛失通信
紛失通信 (oblivious transfer; OT) は送信者の送信する \(n\) 個のデータのうち受信者が \(k\) 個を受信できる二者間の通信プロトコル。ここで送信者は \(n\) 個のうちのどの \(k\) 個が受信されたかを知ることができず、受信者は \(k\) 個以外のデータを知ることができないという暗号論的な性質を持つ。…
基数変換
数の表現ですべての数値に一意の記号を割り当てようとすることは非現実的である。代わりに、古代から有限の記号の組み合わせで任意の数を表現する記数法 (numerical notation) が用いられてきた。現代で一般的に使用されている記数法は位取り記数法 (positional notation) である。…
キャッシュ
キャッシュ (cache) はプログラムやシステムのデータアクセスの高速化を目的としたメカニズムおよびその保存領域。アクセス頻度の高いデータや、次にアクセスされることが予測されるデータ、または生成や取得に時間がかかるデータを一時的に高速に読み取りが可能なキャッシュに保存することでアプリケーションの処理時間を短縮することを狙う。…
乱数検定: NIST SP 800-22
NIST SP 800-22 (1) (または単に NIST 検定) は NIST が 2001 年に刊行した論文による (疑似) 乱数生成器のランダム性を検定するための検定スイートである。この検定プログラムは NIST のサイト (2) からダウンロードできる。
MOXBOX ウィジェット
この MOXBOX で JavaScript や CSS (あるいはサーバサイドの XSLT や REST API など) で実装されたウィジェットおよびツールが正しく機能することを確認するためのページである。このサイトの作者以外には特に有用なものではないが、何かの参考にはなるかも知れない。…
論文翻訳: NIST SP 800-22: A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications / 暗号アプリケーションのための乱数・擬似乱数生成器の統計的検定スイート
NIST SP 800-22 として刊行された (疑似) 乱数生成器のランダム性の検定に関する 2001 年の論文。15 の検定で構成されている。この論文に基づいた検定スイートは NIST SP 800-22: Download Documentation and Software からダウンロードできる。…
乱数検定: RMT 検定
RMT 検定 (random matrix theory test) (1) はデータ列の乱数性を検定するためのアルゴリズム。与えられたデータ列で相互相関行列を作成し、その固有値分布が RMT に基づく理論曲線と一致すれば検定に合格する。
論文翻訳: Min-Wise Independent Permutations (Extended abstract)
min-wise 独立置換族 (min-wise independent permutations family) に関する 1998 年の論文。Brahms サンプリングの関連で調べたもの。(厳密) min-wise 独立 (\(\ref{e4}\))、および近似 min-wise 独立 (\(\ref{e6}\))、制限 min-wise 独立 (\(\ref{e7}\)) の定義。…
論文翻訳: Time, Clocks, and the Ordering of Events in a Distributed System
論理クロック (Lamport タイムスタンプ) に関する 1978 年の論文。
論文翻訳: The Byzantine Generals Problem
ビザンチン将軍問題に関する 1982 年の論文。すべてのプロセスが完全グラフで接続している構成において、署名なしのアルゴリズムでビザンチン将軍問題を解くには \(n \ge 3m+1\) が必要。署名ありのアルゴリズムでは \(n \ge m+2\) が必要。完全グラフではない場合、署名なしアルゴリズムは \(3m\)-正則グラフであればビザンチン将軍問題を解くことができる。…
TRANSCRIBE: Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation
A 1988 paper on Secure multi-party computation. A transcription of an old PDF for the purpose of reading it in machine translation.
TRANSCRIBE: Authenticated Algorithms for Byzantine Agreement
A 1983 paper on asynchronous Byzantine atomic broadcast. A transcription of an old PDF for the purpose of reading it in machine translation.
論文翻訳: Authenticated Algorithms for Byzantine Agreement
非同期ビザンチンアトミックブロードキャストに関する 1983 年の論文。
論文翻訳: Consensus in the Presence of Partial Synchrony
DLS88 として知られる、部分同期モデルおよびクォーラムに関する 1988 年の論文。
TRANSCRIBE: Consensus in the Presence of Partial Synchrony
A 1988 paper on the partial synchronization model and quorum, known as DLS88. A transcription of an old PDF for the purpose of reading it in machine translation; ja
論文翻訳: XFT: Practical Fault Tolerance Beyond Crashes
ビザンチン障害耐性を持つ XPaxos の 2016 の論文。ビザンチン故障、非ビザンチン故障、パーティション分断障害の合計が \(f\) 以下であれば、全体で \(N=2f+1\) プロセスの構成で安全な SMR を行うことができる。
論文翻訳: Synchronous Byzantine Agreement with Expected \(O(1)\) Rounds, Expected \(O(n^2)\) Communication, and Optimal Resilience ラウンド期待値 \(O(1)\)、通信期待値 \(O(n^2)\)、そして最適な回復力を備えた同期ビザンチン合意
2019 年の論文。
論文翻訳: The Sleepy Model of Consensus
暗号論的ハッシュ関数とゼロ知識証明を使ってプロセスごとに固有の乱数を内密に生成し、その値が既定のしきい値 \(\lambda\) より小さければ当選というスキーマの委員会選出を行う Sleepy Consensus に関する 2017 年の論文。Algorand が VRF をハッシュ関数と ZKP に置き換えたようなアイディア。…
論文翻訳: Constant Latency in Sleepy Consensus
検証可能な乱数を用いて委員会選出を行う Sleepy コンセンサスで動的な参加を可能にする 2022 年の論文。
論文翻訳: DiemBFT v4: State Machine Replication in the Diem Blockchain
Diem Blockchain のコンセンサスアルゴリズム DiemBFT (旧名 LibraBFT) に関する 2021 年の論文。この v4 で 2 ラウンドで確定するように修正された。
Winny
Winny (ウィニー) は Freenet をモデルに実装された P2P ファイル共有のためのアプリケーションまたはネットワークである。匿名性の高さと効率的で高速なキャッシュ機構で日本ユーザのコミュニティで広まり、日本の P2P ファイル共有ブーム、およびそれにまつわる違法コピー行為とハッキング被害の代名詞ともなった。…
論文翻訳: Packrat Parsing: Simple, Powerful, Lazy, Linear Time
複数の選択肢をもつ構文解析時に、解析済みのパターンの結果を記録しておき別の選択肢を評価するときに使用する Packrat 構文解析に関する 2002 年の論文。
プレゼンテーション技法
Microsoft de:code 2014 でマイクロソフトのエバンジェリスト西脇さんの「プレゼンの極意」を聞いてからプレゼンの構成や技法について注意深く見るようになった。自分がプレゼンテーションをどう見てるか、どう作っているかについてこのページに書き残しておく。
論文翻訳: Incremental Packrat Parsing
Packrat 構文解析のメモ表を利用して、構文解析済みの入力テキストが変更されたときに (全体の再パースなしに) テキスト変更分をインクリメンタルに構文解析結果に反映する Packrat 構文解析の改良に関する 2017 年の論文。
構文解析
一般に構文解析 (syntactic analysis) とは文章を解析してその構文構造を導き出すという意味を持つ。
形式言語
あるオートマトンによって受理することのできる言語である。
オートマトン
オートマトン (automaton; ムーア型順序機械) は計算理論における数学的なモデルの総称。ある既定の手続きに従って行う自動計算の機構、つまりプログラミングやインタープリタ、文字列解析などを表すモデルとしてしばしば使われている。
組み合わせ合計
組み合わせ合計 (combination sum) 問題は、正の整数の集合 \(\vector{x} = \{x_0,x_1,\ldots\}\) の中から合計が値 \(y\) になるようなすべての一意の組み合わせを選択する問題。ナップサック問題 (Knapsack problem) の一種でしばしばプログラミング課題として用いられる。…
Rust: プロファイリング
ソフトウェア開発におけるプロファイリング (profiling) とは、プログラムのボトルネックやメモリリークを発見することを目的とした CPU 時間やメモリ使用量の計測である。ソフトウェアの最適なパフォーマンスを引き出すためにはソースコードを最適に調整する作業が重要であるが、一般にプロファイリングはその優先順位や費用対効果を推定するための事前調査を目的として実施される。…
eBPF
eBPF (extended Berkeley packet filter) はカーネルの再構築なしにカーネル空間でプログラムを実行することのできる仮想マシン技術。eBPF のバイトコードは実行時に JIT コンパイラによって検証とネイティブコード変換が行われ、カーネル内の保護された空間 (サンドボックス) で安全かつ効率的に実行することができる。…
コード変換
Intel SGX
Intel SGX (Intel Software Guard Extensions) はハードウェアによって暗号化されたメモリ領域を提供する TEE (trusted execution environment) 技術の一つである。クラウド環境やユーザの手元の PC といった信頼性の保証できない環境において、機密性の高いアプリケーションコードやデータを暗号化された空間に隔離し安全に動作できるようになる。…
非同期処理
並行プログラミング
並行プログラミングとは、そのような環境で効率的な処理を実装するために複数のタスクを同時に実行するプログラミング技法である。並行性によりプログラムは一度に多くのタスクを処理することができるが、並行プログラムを書くことはことさら簡単なことではない。スレッドやロックなどの構造を処理し、競合状態やデッドロックなどを回避することは非常に面倒な作業であり、並行プログラミングの作成が困難である理由でもある。…
Rust: tokio による非同期プログラミング
tokio (トーキョー) は Rust 言語で非同期アプリケーションを作成するためのイベント駆動型フレームワークです。煩雑さを排除し統一された方法で使用できる非同期ランタイムおよびノンブロッキング I/O とネットワークのプラットフォームを提供しています。開発者は tokio を使用することで高度にスケーラブルな設計のネットワークアプリケーションを迅速に開発することができます。…
Raspberry Pi: RTC の接続
Raspberry Pi は RTC1 (real-time clock) を搭載しておらず、シャットダウン時に時刻を記録して次の起動時にはその時刻から開始するように動作する。ネットワークに接続していれば起動後すぐに NTP サーバと時刻同期を行って概ね正しい時刻で動作するが、オフライン環境や NTPd をオフにしている状態ではシステム時刻が実際の時刻よりどんどん遅れることになる。…
Raspberry Pi: スピーカーの接続
Raspberry Pi をヘッドレス (画面やキーボードを接続しない) 機器として使用するとき、システムで何かエラーが起きていることを通知する手段が必要である。ネットワークと接続しているのであればメールや LINE Bot 等を使用できるが、そうでない場合は別に物理的な手段を用意しなければならない。…
Raspberry Pi: ディスプレイの接続
必須ではないが Raspberry Pi でやっておくと良い設定や便利なガジェットなどのメモ。また HDMI キャプチャデバイスを使用することでシステムコンソールを Android 端末や PC に表示することもできる。
Raspberry Pi: 動画の撮影
カメラの接続が完了したら Raspberry Pi で動画を撮影してみよう。Raspberry Pi は Pico 以外の全てのモデルに H.264 ハードウェアエンコーダーを搭載していることから、リアルタイムでの映像の加工やフォーマット変換、ストリーミングといった用途も可能である。…
Raspberry Pi: 静止画の撮影
カメラの接続が完了したら Raspberry Pi で静止画を撮影してみよう。Raspberry Pi は通常の Linux OS 環境と同様に USB 接続のカメラが使用できるほか、専用のカメラモジュールを使用して動画や静止画を撮影することができる。
Raspberry Pi: カメラの接続
Raspberry Pi は通常の Linux OS 環境と同様に USB 接続のカメラが使用できるほか、専用のカメラモジュールを使用して動画や静止画を撮影することができる。また Pico 以外の全てのモデルに H.264 ハードウェアエンコーダーを搭載していることから、リアルタイムでの映像の加工やフォーマット変換、ストリーミングといった用途も可能である。…
論文翻訳: WHITE-BOX CRYPTOGRAPHY: HIDING KEYS IN SOFTWARE
ホワイトボックス暗号に関する概要と 2012 年時点の現状をサーベイした論文。
Carillon
ホワイトボックス暗号
ホワイトボックス暗号 (white-box cryptography; WBC) は攻撃者が暗号プリミティブの実装やその実行プラットフォームに対して特権的アクセスを持つ状況においても暗号鍵そのものの漏洩 (つまり鍵復元) を防止することを目的とした難読化 (obfuscation) の手法である。…
論文翻訳: On White-Box Cryptography
white-box 暗号について Q&A 形式で解説する 2008 年の論文。発表当時の状況に依存する記述も多いので現状どうなっているかは追加で知る必要がある。
制御理論
自然に変化する系 (システム) に対して、系が目的の状態となるように系の変化率に作用する入力を外部から人為的に与えることを制御 (control) と呼ぶ。
Ansible セットアップ
Raspberry Pi: GPS レシーバーの接続
Raspberry Pi を含む Linux ベースのシステムに USB 接続の GPS レシーバーを接続することで正確な位置情報を得ることができる。Linux ではシリアルまたは USB 接続された GPS とのインターフェースとなる gpsd というデーモンを利用する。gpsd で確認済みのハードウェアは Compatible Hardware 参照。…
Raspberry Pi: USB ストレージの接続
Raspberry Pi は SD カードから OS 起動する。しかし安価で小さな SD カードは耐久性も低く頻繁な書き込み操作によって寿命が短くなる。データベースのような書き込み操作の多いアプリケーションを動作させるのであれば USB 経由で SSD/HDD ストレージを使用したほうが安心であるし、また書き込み寿命が大きく違わないにしても USB フラッシュメモリをそのような用途にすることでファイルシステム破損時のシステムの再構築の手間を減らすことができる。…
Raspberry Pi: ドライブレコーダー
Raspberry Pi: インストールと基本的な設定
この記事では Raspberry Pi 購入直後の状態から ssh で接続して使用するための必要なセットアップ作業を記述している。
Rust: オブジェクト指向からの移行
EBNF
EBNF (extended Backus-Naur form) は BNF を拡張した構文メタ言語 (syntactic meta-language) の一種。プログラミング言語や HTML のようなデータフォーマットの構文定義を記述することができる。
翻訳: ISO/IEC 14977:1996 Information technology — Syntactic metalanguage — Extended BNF
Extended BNF (EBNF) の ISO/IEC 14977:1996 規格。
論文翻訳: Paxos Made Simple
Paxos に関する 2001 年の論文。独特のユーモラスにより世間にうまく伝わらなかった先の論文 "The part-time parliament" (5) をサマリーしたような内容となっている。
論文翻訳: The Part-Time Parliament
Paxos に関する 1998 年の論文。戯曲めいた説明がしばしば理解を阻害すると言われるので Paxos Made Simple (2001) をあわせて読むと良い。Paxos 島やその議会は Lamport によるフィクションで実在しない。文中のギリシャ文字で表記されている登場人物は実在する計算機科学者を表しているようである。…
論文翻訳: Zab: High-performance broadcast for primary-backup systems
ZooKeeper のプライマリ-バックアップ間でトランザクションのアトミックブロードキャストに使われている ZAB に関する 2011 年の論文。
Federated Byzantine Agreement
Federated Byzantine Agreement (FBA; 連合ビザンチン合意) は合意に参加する参加者それぞれの信頼に基づくクォーラム (quorum) と呼ばれる部分ネットワークを形成する P2P 向けのコンセンサス機構である。従来のビザンチン合意 (BA; Byzantine Agreement) 機構と比べてノードの参加が自由である (permissionless) という点が大きな特徴となっている。…
論文翻訳: Conflict-free Replicated Data Types
因果一貫性を使用する Version Vector のような並行する更新を追跡できるシステムで自動的に競合を解決できるデータ型についての 2011 年の論文。
Blockchain: コンセンサス
一般的な分散システムの文脈でのコンセンサスは、一貫性 (consistency) を達成するための役割選出 (リーダー選挙)、合意、同期、競合の解決や調整といったメカニズムを包括的に指した言葉である。しかし、ブロックチェーンに関する論文やブログではコンセンサスが内包するこれらのメカニズムを分解しないまま論議がなされており、中には選出メカニズムと合意メカニズムが同列で比較されているような間違いも起きている。…
Version Vector
Version Vector (VV) は並行して発生するイベントの因果関係 (causality, happened-before relation) を追跡するための機構。因果一貫性 (causal consistency) と呼ばれる一貫性モデルにおいて、競合する更新の因果関係を追跡しながら表現するために使用されている。…
論文翻訳: Scalable and Accurate Causality Tracking for Eventually Consistent Stores
結果整合性を持つ Key-Value ストア間で更新の競合を検出し追跡するための機構である Version Vector を、空間的および時間的に効率化した Dotted Version Vectors (DVV) および Dotted Version Vector Sets (DVVS) に関する 2014 年の論文。…
論文翻訳: Detection of Mutual Inconsistency in Distributed Systems
バージョンベクトル (version vector) と起点 (origin point) を使用して、特定ファイルの複数のコピーに対して独立して行った操作による相互不整合 (mutual inconsistency) を検出する方法についての 1983 年の論文。
ビジネス: ブックマークやメモ
論文翻訳: Concise Server-Wide Causality Management for Eventually Consistent Data Stores
ノード論理クロックとキー論理クロックを使用して分散システムにおけるデータ更新の因果関係を追跡するための 2015 年の論文。
Rust: ベンチマークの計測
暗号プリミティブのパフォーマンス比較
ゼロ知識証明
ゼロ知識証明 (ZKP; zero-knowledge proof) は、ある命題 (statement) が真であるという証明者 (prover) の主張を、それ以上の情報を明かすことなく検証者 (verifier) が確実に知る (受理する/拒否する) ことのできるスキームである。…
Banded Hash Tree
現実的なストレージに対して追記効率が良く、累積的な構造変化の完全な履歴を保持するリスト構造 Banded Hash Tree (BHT) について説明します。この構造はデータの追加が可能なハッシュツリー (Merkle ツリー) であり、一般的なハッシュツリーと同様に小さなデータ片を用いてデータの破損や改ざんを検証することができます。…
Rust: スレッド間のデータ共有パターン
論文翻訳: The latest gossip on BFT consensus
Tendermint のコンセンサスに関する 2018 年の論文。
論文翻訳: BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory
NVM (不揮発性メモリ) 向けデータ構造 BzTree に関する 2018 年の論文。Microsoft US #10599485 特許。
PlusCal: 証明アプローチ
このページでは PlusCal を使って記述したシステムが正しいことをどのように証明するかについて説明する。サンプルを実行するための環境セットアップは環境設定と検証の実行を参照。
GraalVM
GraalVM は Java や Scala などの JVM 言語、C/C++ や Rust などの LLVM 言語、および JavaScript や Python のような動的型付言語などに向けた高性能ランタイムである。GraalVM を使用することでそれらのプログラミング言語間の相互運用を効率化し、また AOT (ahead of time) コンパイラによって Java アプリケーションを事前にコンパイルして起動時間を短縮しメモリのオーバーヘッドを削減したネイティブ実行ファイルを作成できる。…
GraalVM: 入門
翻訳: PlusCal/TLA+: An Annotated Cheat Sheet
PlusCal と TLA+ のリファレンスとして有用なチートシート。
翻訳: The PlusCal Algorithm Language
TLA+ と PlusCal
TLA+ (temporal logic of actions plus; 1999年) と PlusCal (2009年) は共に並行処理と分散システム向けに設計された仕様記述言語 (高レベルモデリング言語)。システム設計やアルゴリズムなどの重要で危険度の高い部分のエラーを定性的に検出することを目的としている。…
PlusCal: 並行システムと非同期処理
このページでは PlusCal を使ってマルチプロセスやマルチスレッド、それらに伴う非同期処理といった並行処理を記述する方法について説明する。サンプルを実行するための環境セットアップは環境設定と検証の実行を参照。
PlusCal: 制御構造
このページではいくつかの例を使って PlusCal の基本的な制御構造を説明する。実行環境のセットアップは PlusCal を参照。
git: 大規模なマージ
想定: あなたのチームはあるリポジトリ Alice 1.x をフォークしていくつかの機能を修正した Bob 1.x を開発している。いままで Alice 側の修正は alice/master ブランチ上の v1.x.y リリースタグを bob/develop にマージすることで取り込んでいた。…
翻訳: A PlusCal User's Manual
PlusCal: データ構造と演算子
英語: 意思伝達のための必須表現
英語
英語のフレーズなどを記述しておくノート。
TLA+入門2: 独立した 2 変数のシステム
このページでは TLA+ の例として時相論理演算子を扱う。
TLA+入門1: TickTack
このページでは最初の TLA+ の例として、システム状態に 0 と 1 を交互にとる TickTack システムについて考える。
PlusCal入門1: hello, world
このページでは最初の PlusCal の例として hello, world と表示するプログラムをレビューし、その基本的な記述構造について考える。PlusCal での仕様記述や TLC 実行のための環境設定は環境設定と検証の実行を参照。
翻訳: Summary of TLA+
記号論理
記号論理 (symbolic logic) は論理的な推論を数学的記号法を用いて研究する分野。
システム稼働率
システム稼働率 (system availability factor) はシステムに期待できる可用性の指標である。
wasmer
wasmer は OS やチップセットから隔離された環境で WebAssembly バイナリを実行できる軽量な仮想マシン。
Rust: Non-blocking I/O programming with mio::Poll
Linux カーネルのシステムコール epoll や FreeBSD (Mac OS) の kqueue、またはより古典的な POSIX 準拠の select や poll システムコールは大量のクライアント接続を効率的に処理するノンブロッキング I/O プログラミングに必要な機能である。…
論文翻訳: Bulletproofs: Short Proofs for Confidential Transactions and More
高速でデータサイズの小さいレンジプルーフ (範囲証明) のゼロ知識証明である Bulletproofs に関する 2018 年の論文。
Rust: async を使った非同期処理
Bumblebees
Bumblebees は互いに非同期メッセージを交換する 2 つのピアアプリケーション向けプロトコル。シンプルな概念と 4 種類のメッセージを使用して、代表的な以下のネットワーク機能を実装することを目的としている。
Bloom Filter
Bloom Filter (ブルームフィルタ) は大規模データセットに対する近似メンバーシップクエリー (approximately membership query)、つまり特定の要素が含まれているかを効率的にテストするための確率的データ構造。false positive (偽陽性; 含まれていないのに true となること) を許容するが false negative (偽陰性; 含まれているのに false となること) は発生しないという特徴を持つ。…
Home-built Computers
論文翻訳: Fast Multiparty Threshold ECDSA with Fast Trustless Setup
ポスト量子暗号
ポスト量子暗号 (PQC; post-quantum cryptography) は量子計算耐性を持つ暗号アルゴリズムのこと。現在広く使用されている暗号アルゴリズムの多くは素因数分解問題 (RSA など)、または離散対数問題 (楕円曲線や BLS など) の困難性に基づいている。…
ハッシュベース暗号
ハッシュベース暗号 (hash-based cryptography) は素因数分解や離散対数のような数学的な問題の困難性を利用するのではなく、暗号論的ハッシュ関数によって確立されるセキュリティに基づいている。量子計算機を使用して暗号論的ハッシュ関数の衝突と見つけることが困難であると同様に、ハッシュベースの暗号も量子計算耐性を持つと考えられている。…
Mix Network
Mix Network は受信者のみが解読できる暗号でメッセージを秘匿し、さらにランダムに選んだ多段のノードで中継させることでメッセージの発信者や伝達経路と通信内容の両方を秘匿することを目的としたネットワーク。メッセージを中継するノードを一般にルーター (router) と呼ぶ。…
Kademlia
Kademlia は二分木構造に基づくシンプルで実用的な分散ハッシュテーブル (DHT; distributed hashtable) アルゴリズム。ネットワークの中から目的のノードを効率よく検索することのできる分散オブジェクトロケーション/ルーティング (DOLR; decentralized object location and routing) の一つである。…
論文翻訳: Kademlia: A Peer-to-peer Information System Based on the XOR Metric
二分探索木に基づき距離関数に XOR を使用する分散ハッシュテーブルアルゴリズム Kademlia に関する 2002 年の論文。ネットワーク全体では二分木の構造だが、個々のノードのルーティングテーブルはその部分木として見ることのできるリスト構造となる。ルーティングテーブルの参照先は \(k\)-bucket にまとめられ、駆動時間の長いノードは後の生存率も長いという統計的事実からどのノードを参照するかを決定する。…
Chord
Chord はコンシステントハッシュ法 (consistent hashing) に基づく分散ハッシュテーブルである。対数メッシュのリンクを内包する論理リングで表される。
論文翻訳: Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications
Consistent Hashing を使用した分散ハッシュテーブルアルゴリズム Chord に関する 2001 年の論文。2003 年に似た内容で新しい論文 (2) が出ているのでそちらを参照したほうが良いかも知れない。
Tapestry
Tapestry(2,3) は PRR の論文(1)に基づいた Prefix ルーティングを行う分散ハッシュテーブルルゴリズム。RPP にノードの参加と離脱のアルゴリズムが追加されている。各ノードは SHA-1 を使用した ID (アドレス) が割り当てられ、アプリケーションにもエンドポイント GUID が割り当てられる。…
Peer to Peer
P2P (peer to peer) は対等な動作をする (明確な主従関係を持たない) ノードによるネットワークまたはシステムのモデル。従来のクライアント/サーバシステム (C/S システム) におけるサーバがクライアントに対して一方的にサービスを提供する役割だったのに対して、P2P ではそれぞれのピアが状況に応じてサーバとクライアント両方の役割を持つ。…
P2P ファイル共有
P2P ファイル共有は P2P ネットワーク技術を使用したファイルの配布と共有を行うサービス、アプリケーションまたはネットワーク。ダウンロードのネットワーク負荷をユーザ側で分散することから低コストでサービスを運営することができるが、一方で、データの管理を行うことができず、著作権管理や情報漏えいと言った法的な問題に巻き込まれることも多い。…
有向非巡回グラフ
DAG (directed acyclic graph; 有向非巡回グラフ) は有向グラフの中でも閉路をもたない (つまり一度通過した頂点にふたたび戻ることはない) 構造を持つグラフ。ソフトウェアの分野ではジョブ管理システムやビルドシステム、ネットワーク問題で扱う。
分散ハッシュテーブル
分散データベースにおいて目的とするオブジェクトを効率的に検索するために特定のスキームに基づいてネットワークに配置する方法を分散オブジェクトロケーション/ルーティング (DOLR; decentralized object location and routing) と呼ぶ。一般的にはオブジェクト識別子をノードのアドレス空間にマッピングすることで行われる。…
Merkle Tree
マークルツリー (Merkle tree; ハッシュ木) はあるデータセットのハッシュ値を再帰的にハッシュ化することで得られるツリー構造。このツリーのルートにあたるルートハッシュはすべてのデータのハッシュ特性を含んだ固定サイズの値であるため、後で一部のデータを検証するのに都合が良い。…
非復元ランダムサンプリングにおける公平性
Inverse (逆数) の重み分布に対して ×1,000 を実行してみれば明らかなように、それぞれの要素の選択頻度の分布 (Actual Win Rate) は重みの分布とはかけ離れた挙動となる。唯一一致する分布は Flat だけだが、これはすべての要素の重みが等価であることから一様ランダムサンプリングと同じ意味である。…
読書メモ: Science Research Writing for Non-native Speakers of English
英語が母国語ではない研究者が英語で研究文書を作成するためのガイド本。
InterPlanetary File System
IPFS (InterPlanetary File System) は Protocol Labs 社を中心に開発されている P2P 技術を使用したファイル配信のための分散ストレージおよびそのプロトコルの名称である。Gnutella や BitTorrent といった P2P ファイル共有と同類の技術だが、Web (HTTP) に代わるプロトコルや分散ファイルシステムとなることを目的としている。…
χ² 検定
χ² 検定 (chi-square test) は χ² 分布を確率分布とする確率変数 \(\chi^2\) を求めることで行う検定。その利便性によって広く普及している。期待した分布と観測した分布が適合しているかを調べる適合度検定と、2 つの事象が関連しているかを調べる独立性検定がよく利用されている。…
F 検定
F 検定 (F test) は 2 つの標本の分散 (標準偏差) が異なっているかを測定する統計的仮説検定。代表的な利用例は t 検定の予備検定である。
t 検定
\(t\) 検定 (t-test; スチューデントの t) は正規分布に従う母集団から無作為に抽出した 2 つの標本が互いに異なるかを計測する仮説検定である。母集団の標準偏差が不明な場合は Z 検定の代わりに t 検定を使用する
東京都人口統計のデータ
以下の 2 つの CSV ファイルは東京都の人口（推計）－過去の推計－の「次の国勢調査人口が公表されるまでの人口推計」から入手できる (人が読む形式の) Excel 形式の統計表1から抽出した数値をプログラムから利用できる形式で出力したものである (いつ時点のデータかは version カラムを参照)。…
統計的仮説検定
観測値の背景にある母集団の構造を仮定し、観測値の統計からその仮定が受け入れられるか、さもなくば拒否されるかを判断する統計的手法を統計的仮説検定 (statistical hypothesis testing) と呼ぶ。このとき仮定した構造のことを仮説 (hypothesis) と呼ぶ。…
論文翻訳: Fast Generation of Discrete Random Variables
Walker のエイリアス法を改良して正方ヒストグラムを使う方法で高速に重み付きランダムサンプリングを行うアルゴリズムに関する 2004 年の論文。
ランダムサンプリング
ランダムサンプリング (RS; random sampling) は統計学やデータ分析において大規模な集合 (母集団) から無作為にデータを抽出する手法である。母集団の各要素が等しい確率で選ばれるサンプリングでは、得られたサンプルは母集団全体の特性を統計的に正しく反映していることが期待される。…
論文翻訳: Weighted Random Sampling (2005; Efraimidis, Spirakis)
重み付きランダムサンプリング (乱択) のアルゴリズムに関する 2005 年の論文。重み付き非復元ランダムサンプリング (weighted random sampling without replacement) に基づいて、開始時点でサイズが未知の母集団から 1 パスでサイズ \(m\) の部分集合を生成することができる。…
XML: Extensible Markup Language
XML (extensible markup language) は構造化されたデータを表現するための W3C が規定するマークアップ言語。ドキュメント指向のデータ向けに高機能で非常に高い柔軟性と拡張性を持っており、また人間が読みやすいように設計されているため、データ交換から設定ファイルまで様々な分野で広く使用されている。…
XPath: XML Path Language
XPath (XML path language) は、主に XSLT で使用されるクエリー言語である。XML 文書上で目的のノードを特定するアドレッシングや、ノード集合から特定のノードを抽出するフィルタリングを行うことを目的としている (目的としてはリレーショナルデータベースに対する SQL に似ている)。…
XML-Schema
XML Schema は XML 文書の構造と内容を定義するためのスキーマ言語である。スキーマには XML によるインターフェースを定義し、XML 文書の整合性を検証することでデータの信頼性と相互運用性を高める役割がある。
論文翻訳: Efficient and Scalable Multiprocessor Fair Scheduling Using Distributed Weighted Round-Robin
優先度を重みづけされたプロセッサにラウンドロビンでジョブを割り当てるアルゴリズムに関する 2009 年の論文。
雑記: 2019 新型コロナウイルス
格子暗号
格子暗号 (lattice-based cryptography) は多次元の格子構造を用いた公開鍵暗号スキーム。証明可能な強力なセキュリティの保証や量子計算耐性、完全準同型暗号へ応用可能といった特性を持っている。
読書メモ: スパンプログラム
Karchmer and Wegderson は 1993 年にブール関数を計算する興味深い線形代数モデルスパンプログラム (span program) を発表した。ある関数 \(f(x_1,\ldots,x_n)\) に対するスパンプログラムは、変数 \(x_i\) とその否定 \(\bar{x}_i\) でラベル付けされた行を持つ、ある体 (field) 上の行列として表される (一つの変数が複数の行をラベル付けしてもよい)。…
準同型暗号
準同型暗号 (homomorphic encryption; HE) は暗号化したデータを復号化せず演算することで、復号化により計算結果を得ることができる暗号スキーム。データの内容を秘匿したままクラウドのようなサードパーティの計算リソースを使用することができる。準同型暗号の概念は最初に (1) で紹介された。…
論文翻訳: On Span Programs
Span Program に関する 1993 年の論文。
論文翻訳: DFINITY Technology Overview Series Consensus System
Dfinity のテクニカルオーバービューを記述した 2018 年の論文。公証 (notalization) がブロックの承認を表している? 少し用語の言い替えがある。
疑似乱数生成
乱数 (random number) はランダムに選択された数のこと。特定の出現パターンを持たず、選択される値が予測できないという性質を持っており、ゲームや科学技術シミュレーション、暗号セキュリティの分野で重要な役割を持っている。
論文翻訳: Xorshift RNGs
ビット演算のみを使用した非常に高速でコンパクトな Xorshift 擬似乱数生成アルゴリズムに関する 2003 年の論文。著者はキャリー付き乗算の論文にも携わっている。Abstract にあるようにこの論文自体はアイディアの説明であり、良い乱数・悪い乱数で何点かの間違いが指摘されている。…
Rust: nom によるパーサー実装
nom は Rust で実装された字句解析ライブラリ (Lexer, Lexical Analyzer, Tokenizer) およびパーサコンビネーターです。プログラムのソースコードや DSL (domain specific language) のようなテキストデータの字句解析を実装できるのに加えて、バイナリデータの解析も前提に設計されています (実際、nom の作者は nom を使って GIF 画像ファイルのデコーダーを実装しています)。…
論文翻訳: Graph learning: How humans infer and represent networks
話し言葉や音楽といった人間が認知できる刺激ははグラフ構造で表すことができる。人間がどのように時系列のグラフ構造を認識しているかに関する最近の研究をまとめた 2019 年の論文。
公開鍵暗号アルゴリズム
公開鍵は「A から B を計算するのは容易だが B から A を計算するのは困難」といった計算の非対称性を利用した暗号アルゴリズム。公開鍵アルゴリズムを応用した技術として鍵共有、暗号、電子署名が広く使われている。また近年では公開鍵の特性を利用してゼロ知識証明といったようなアルゴリズムの研究も進んでいる。…
RSA 暗号
RSA 公開鍵暗号 (RSA public-key encryption) は大きな数の素因数分解の困難性を利用した公開鍵暗号。最初の実用的な公開鍵暗号で 2000 年に特許が切れている。より鍵の小さい楕円曲線暗号に置き換えられつつあるが現在においても広く利用されている。
離散対数問題と公開鍵暗号
離散対数問題に基づく暗号アルゴリズムは古くから研究されてきたが、公開鍵暗号が世間に広く利用されるようになったのは素因数分解に基づく RSA を待たなければならなかった。しかし旧来の欠点を克服した DSA や、楕円曲線への応用によって、近年では RSA に比べてより高いパフォーマンスを得られるようになった。…
楕円曲線暗号
楕円曲線は離散対数問題に対して有限体よりも効率的で高いセキュリティを持つ有限体である。これらはどちらも DLP の数式上の循環群 \(G\) として使用できるため、旧来の Diffie-Hellman や ElGamal といったアルゴリズムをほぼそのまま楕円曲線に置き換えることができる。…
論文翻訳: On the Size of Pairing-based Non-interactive Arguments\(\star\)
2016 年の論文。
論文翻訳: Pinocchio: Nearly Practical Verifiable Computation
論文翻訳: Quadratic Span Programs and Succinct NIZKs without PCPs
論文翻訳: High-speed high-security signatures
楕円曲線暗号アルゴリズムの一種であるエドワーズ曲線デジタル署名 (EdDSA; ed25519, ed448) の速度やセキュリティ優位性に関する 2011 年の論文。
RFC翻訳: Edwards-Curve Digital Signature Algorithm (EdDSA)
論文翻訳: Curve25519: new Diffie-Hellman speed records
通常の楕円曲線アルゴリズム (EC) より高速で鍵の小さい Curve25519 を使用した暗号計算に関する 2006 年の論文。
読書メモ: プログラミング言語 Rust 公式ガイド
The Rust Programming Language (日本語版) の邦訳版で ASCII DWANGO から出版されている「プログラミング言語 Rust 公式ガイド」の読書メモ。レベルとしては1つ2つの汎用プログラミング言語を使いこなすことができるプログラマ向けの入門書で、特に C/C++ と関数型言語を使える人ならすんなり読める内容だろう。…
秘密分散共有
秘密分散共有 (secret sharing) または単に秘密分散は秘密情報 \(S\) を \(n\) 個の分散情報に符号化する暗号化アルゴリズムの一種。特に (k,n) しきい値法では \(n\) 個の分散情報のうち任意の \(k\) 個が揃えば元の秘密情報 \(S\) を再構築することができる (\(k\) 個に満たない場合は再構築することができない)。…
論文翻訳: Compact Multi-Signatures for Smaller Blockchains
マルチ署名、公開鍵集約を使用してブロックチェーンサイズを小さくするための 2018 年の論文。
群論
集合とその演算や作用によって定まる構造を代数的構造という。ある集合 \(G\) 上の要素 \(a,b \in G\) に対して \(c = a \ast b \in G\) となるような何らかの演算 \(\ast\) が定義されているとき、集合 \(G\) は代数系であり \((G,\ast)\) や単に \(\mathbb{G}\) と表される。…
論文翻訳: Aggregate and Verifiably Encrypted Signatures from Bilinear Maps
GAP Diffie-Hellman と双線形写像を使用して BLS 署名派生スキーム、集約署名、ブラインド署名、リング署名を紹介する 2003 年の論文。集約署名は異なるユーザによる異なるメッセージに対する署名を単一の署名に集約する
翻訳: Introduction to Transaction Management
論文翻訳: Byzantine Finality Gadgets
Polkadot で検討されている、重み付き PoW を使った分岐の発生するコンセンサスにファイナリティ特性を追加するための PoS に基づいたアルゴリズムに関する 2019 年の提示文書。原文は誤字、脱字、曖昧で難解な言い回しが多く非常に読みづらい。
Blockchain: Polkadot
Blockchain: 用語
鍵共有アルゴリズム
暗号技術における鍵共有 (key exchange) とは、共通の秘匿情報を持たない当事者間で公にされている情報のみを用いて、すべての当事者サイドで通信内容を保護するための共通の鍵を生成する方法。現代の暗号通信では通信の双方が共有鍵 (もしくはそのシード) を作成するために使用している。…
ペアリング暗号
ペアリング暗号 (pairing-based cryptography) は双線形写像 (bilinear map) の構造を持った暗号アルゴリズム。楕円曲線暗号ではある同一の群 \(G\) 上での写像 \(e:G \times G \to G\) の写像だったが、ペアリングでは 2 つの暗号化群から別の群への写像 \(e:G_1 \times G_2 \to G_T\) という構造を持つ。…
Unihertz Atom
Uniherts Atom は小型軽量で防水、防塵に対応したいわゆるタフネス携帯。
論文翻訳: Short Signatures from the Weil Pairing
Gap Diffie-Hellman 群でのヴェイユペアリングを使用することで、一般的な RSA や DSA での署名と比べて同じ強度で短い署名を生成する方法を示す 2001 年の論文。
論文翻訳: Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme
(8) の Gap Diffie-Hellman 群を 1) BLS 署名を秘密分散のスキームに拡張したしきい値署名、2) 複数の署名分散から一つの署名を作成するマルチ署名、3) メッセージを秘匿するブラインド署名のそれぞれに応用した 2002 年の論文。
論文翻訳: Practical Threshold Signatures
RSA に基づく非インタラクティブな署名分散の方法についての 1999 年の論文。
論文翻訳: Verifiable Random Functions
Verifiable Random Function
VRF (verifiable random function) は公開鍵ペアを使用する暗号学的ハッシュ関数である。VRF 関数は秘密鍵を使ってある入力値に対するハッシュ値を算出することができる。加えて、第三者がその公開鍵を使って、受信したハッシュ値が本当にその秘密鍵を使って生成されたものであるかを検証することができる。…
論文翻訳: HotStuff: BFT Consensus in the Lens of Blockchain
State Machine Replication を行うための BFT 合意アルゴリズム HotStuff に関する 2019 年の論文。ブロックチェーンのような頻繁なリーダー変更を行う環境向けに、通信コストが \(O(n^2)\) から \(O(n)\) となっている。
属性ベース暗号
属性ベース暗号 (ABE; attribute-based encryption) は特定の属性を持った対象者のみが情報を復号化できる暗号方式。共通鍵暗号や公開鍵暗号は暗号化/復号化に使用する鍵が 1:1 であるのに対して、それが 1:n や n:1 という特徴を持つ。秘密分散と ID ベース暗号で構成されている。…
論文翻訳: Algorand: Scaling Byzantine Agreements for Cryptocurrencies
PoS に VRF (Verifiable Random Function) を組み合わせた選出を行う BFT 合意アルゴリズム Algorand に関する 2017 年の論文。
Tendermint
論文翻訳: Practical Byzantine Fault Tolerance
Byzantine Fault Tolerance 合意アルゴリズムを実装面で補強した 1999 年の論文。
ビザンチン障害耐性
BFT (Byzantine fault-tolerance) またはビザンチン障害耐性はビザンチン障害プロセスが含まれていても安全な合意を達成することのできる性質である (あるいはその性質を持つ合意アルゴリズムを BFT とも呼ぶ)。またそのような性質を持つ合意をビザンチン合意 (Byzantine agreement) と呼ぶ。…
CAP 定理
CAP 定理は分散データベースシステムにおいてネットワーク分断 (partitioning) が発生したときに一貫性 (consistensy) か可用性 (availability) のどちらかしか取ることができないという原則。一般的な定理や原理といった強い制約ではなく、現在では分散データベースの特性や傾向、設計方針を分類する目的の言葉として使用されている。…
論文翻訳: Reaching Agreement in the Presence of Faults
ビザンチン故障を含むネットワークでの分散合意が可能な条件についての 1979 年の論文。
Bitcoin
Go: インストール
翻訳: Verifiable Random Functions (VRFs)
Verifiable Random Functions (VRF) は公開鍵をキーとする暗号化ハッシュのバージョンである。秘密鍵の所有者のみがハッシュを算出できるが、公開鍵を持つ人であれば誰でもハッシュの正当性を検証できる。VRF はハッシュに基づくデータ構造の列挙を防ぐのに役に立つ。…
論文翻訳: In Search of an Understandable Consensus Algorithm (Extended Version)
Raft は複製されたログを管理するためのコンセンサスアルゴリズムである。これは (Multi-) Paxosと同等の結果を生み出し Paxos と同程度に効率的だが、その構造は Paxos とは異なる; Raft によって Paxos よりも理解しやすく実用的なシステムを構築するためのより良い基盤が提供される。…
Java: 公開鍵生成アルゴリズム
Java では KeyPairGenerator クラスを使用して作成することができる。
論文翻訳: Impossibility of Distributed Consensus with One Faulty Process
コンセンサスの問題にはプロセスの非同期システムが含まれており、そのいくつかは信頼性が欠落していることがある。課題は、信頼できるプロセスが 2 値の下で合意することである。本論文では、この課題に対するどのようなプロトコルであっても、たった 1 つでも不完全なプロセスが含まれるのなら終了に達しない可能性を持つことを示している。…
分散システム
分散システム (distributed system) は、クライアント (エンドユーザ) から単一のシステムとして見えるように動作する、協調して動作する複数のコンピュータで構成されるシステム。複数のコンポーネントが異なるノードに配置されており、個別のノードが故障してもシステム全体がそれを見せないように動作し続けることができる。…
論文翻訳: Skip Graphs
Skip Graph は、要素を格納する分散システムでバランスツリーの全機能を提供する、Skip List に基づく新しい分散データ構造である。要素はいつでも失敗する可能性のある別々のノードに格納される。これらは peer-to-peer ネットワークでの検索に使用されるように設計されており、キーの順序付けに基づいてクエリーを実行する機能を提供することで、ハッシュテーブル機能のみを提要する既存の検索ツールを改善している。…
etcd
etcd (etc distributed) は Raft に基づいた分散トランザクションを実装した分散 Key-Value ストア。コンテナ仮想化に特化した軽量 Linux ディストリビューションである CoreOS においてコンテナ間で設定を共有するために実装されたが、移植性の高い golang で実装されているため現在では様々な OS に移植されている。…
Java: Transport Layer Security
TLS (transport layer security) は TCP 上で安全な通信を行うためのプロトコル。PKI (public key infrastructure; 公開鍵基盤) に基づいて通信相手を認証し、暗号化されたストリームを通じて改ざん不可能なデータのやり取りを行うことができる。…
OpenSSL リファレンス
複雑な OpenSSL コマンドを目的別にまとめる。
メッセージ認証コード
メッセージ認証コード (MAC; message authentication code) はメッセージの完全性を認証付きで保証する暗号学的手法である。鍵の所有者 \(A\) によりメッセージが発行されてから破損や改ざんを受けていないことを同じ鍵の所有者 \(B\) が検証することができる (\(A\) と \(B\) は同一でも良い)。…
クロック同期
ゴシッププロトコル
ゴシッププロトコル (gossip protocol, gossipping) または感染プロトコル (epidemic protocol) はネットワーク上で情報をマルチキャストする方法の一つ。現実社会でうわさ話や感染症が伝播する過程と似たモデルのプロトコルである。ランダムグラフに基づく非構造化 P2P ネットワークや、強い調整者の存在しない分散ハッシュテーブルといった分散システムにおいて、緩やかな方法で最新の情報を共有する (anti-entropy) 目的でよく使用されている。…
Upper Intermediate S
英語のフレーズなどを記述しておくノート。
Service Provider Interface
SPI (service provider interface) は特定のインターフェースに一致する実装を Java のエコシステムが検出して暗黙的にロードするための機能。Java 6 において正式に導入された。アプリケーションは SPI を利用することで実行時に拡張可能な設計を行うことができる。…
Java: 署名アルゴリズム
Java では Signature クラスを使用して任意のメッセージ (バイナリデータ) に対して電子署名を作成することができる。
Java: ハッシュ関数
ハッシュ関数 (hash function)、または Java ではメッセージダイジェスト (message digest) と呼ばれる機能は、ある任意の大きさのバイナリデータから固定長のバイナリを生成するためのアルゴリズムである。データ破損を検出するチェックサム (checksum) と似ているが、以下のような特徴を持つ。…
プライベート認証局
ハッシュ関数
ハッシュ関数 (hash function) は任意長のビット列をある固定の長さのビット列に変換する関数。この操作は \(h\) は数学記号で \(h: \{0,1\}^* \to \{0,1\}^k=\{0,\ldots,2^k-1\}\) と記述することができる。ここで出力ビット長 \(k\) は 256 や 512 といった比較的小さな値である。…
Rocks DB
Rocks DB は C++ で実装された key-value ストアの組み込み用ライブラリ。key 及び value は任意のバイナリデータが使用できる。メモリや極低レイテンシーな Flash ドライブのような物理ストレージと他コア CPU の実行環境に最適化されている。
翻訳: The ZILLIQA Technical Whitepaper
既存の暗号通貨及びスマートコントラクトプラットフォームはスケーラビリティの問題を抱えている。すなはち、1秒間に処理できるトランザクションの数が制限されており、通常 10 未満であることが知られている。パブリック暗号通貨およびスマートコントラクトプラットフォームを利用するアプリケーションの数が増えるにつれ、数百から数千 Tx/s オーダーの高いトランザクションレートを処理することに対する需要が高まっている。…
Blockchain
分散システムにおけるブロックチェーン (blockchain) とは、ビザンチン障害耐性をもつ分散合意アルゴリズムを使ったステートマシンレプリケーション (SRM) として機能する Peer-to-Peer ネットワークである。特に、合意によって生成された命令シーケンスは暗号技術を使用してリンクされた不変のブロックのリストとして分散共有される (データ構造の文脈ではこのブロックのリストをブロックチェーンと呼ぶ)。…
Proof of Work
Proof of Work (PoW) は何らかの作業を行ったことを証明することで目的の行為を行う許可が与えられるスキームである。サービス要求者に何らかの作業を強制することで、DoS 攻撃やスパムメールの送信といった短時間で大量の要求を繰り返して発行する悪意的なコンピューティング能力を利用を防止するための実用上の対策である。…
Practical Byzantine Fault Tolerance
PBFT (practical Byzantine Fault Tolerance) はビザンチン障害耐性をもつ分散合意アルゴリズムの 1 つ。それ以前に提案されていた研究レベルのいくつかの BFT アルゴリズムを改良し、実用的に利用できる水準となった最初の BFT アルゴリズムである。…
Resource Pooing 実装
リソースプーリング (resource pooling) は有限のリソースをプールしアプリケーション内の複数の処理で共有 (resource sharing) する仕組み。一般的に、生成や消滅のコストの高いリソースを初期化を終えた状態で共有、再利用することによるパフォーマンス向上の効果を目的としている。…
Future 機能
CompletableFuture は Java での非同期プログラミングで使用するクラス。非同期プログラミングはアプリケーションのメインスレッドとは別のスレッドを使用して非ブロッキングにタスクを行うための手段である。一般にこのような並列化によってプログラムのパフォーマンスは大幅に向上する。…
HDFS
HDFS (Hadoop distributed file system) は Hadoop で使用されている分散ファイルシステム。データを複数の計算機上に分散配置し、MapReduce を用いて各計算機上で並列分散処理を行うことができる。
Redis:インストール
Redis は C で書かれており、gcc や libc 以外に依存するライブラリを持たないことから公式の Redis Quick Start では最新版をソースからコンパイルすることを薦めている。ここでは開発環境として利用するために Docker や OS 標準のパッケージ管理を使用する。…
Redis
Redis はデータベースやキャッシュ、メッセージブローカーとして使用することのできるインメモリデータベース。NoSQL DB の一つとしてよく知られている。主に Unix 系の OS を対象としており Windows での実行は難しい。
Lettuce 5
覚知の限界
交渉や駆け引きにおける注意の狭窄と焦点化、またそれらによって引き起こされる合理性の欠ける判断は覚知の限界 (bounded awareness; Bazerman, Chugh, 2005) と呼ばれる。
Keras: 超解像
超解像 (super resolution) は解像度の低い画像や動画、音声などの信号からより高解像度なバージョンを生成する技術。
オープンデータセット
畳み込みニューラルネットワーク
畳み込みニューラルネットワーク (convnet, CNN; convolutional neural network) はフィードフォーワード型の深層ニューラルネットワーク (DNN; deep neural network) の一種。主に画像や映像に対する物体認識分野において良好な性能を示している。…
Keras: CNN中間層フィルタの可視化
Matplotlib TIPS
論文翻訳: Deep Clustering for Unsupervised Learning of Visual Features
概要: クラスタリングはコンピュータ・ビジョンで広く適用され研究されている教師なし学習方法の一種である。しかし大規模なデータセット上での視覚的特徴量の end-to-end 学習にクラスタリングを適用させる研究は殆ど行われていない。本研究では、ニューラルネットワークのパラメータと、その結果として得られた特徴量のクラスタ割り当てを組み合わせて学習するクラスタリング手法である DeepCluster を提示する。…
OpenCV: 画像クラスタリング (PCA/DBSCAN)
React:逆引き
Ubuntu18.04: CUDA+Docker セットアップ
Ubuntu 18.04 (bionic beaver) の Docker コンテナ上からホストに設置されている GPU を使用するための環境構築手順を記述する。
ローカルサーバ: Cobalt
CPU 処理と常時起動サーバのためのマシン。
Keras: 画像生成 (変分オートエンコーダー)
オートエンコーダー (autoencoder, 自動符号化器) はニューラルネットワークを使用した次元削減手法。次元の小さい中間層を設置した多層ニューラルネットワークを、入力と同じデータを出力するように学習することで、中間層部分の出力からより特徴的な表現を少ない次元で得ることができる。…
Keras: CNN画像分類 (Keras-provided CNN)
Keras は過去のコンテストで優秀な成績を収めた CNN がすぐに利用可能な形で含まれている。ここではこれらの CNN を独自のデータセットで学習して画像分類を行う。
Keras: CNN画像分類 (クラスの可視化)
Keras: CNN中間層出力の可視化
Keras 2.2 を使用して CNN の中間層がどのような出力を行っているかを可視化する。ここでは学習済みモデルに VGG16 + ImageNet を使用しカワセミの写真のどの部分を特徴としてとらえているかを示すためのヒートマップを作成する (このヒートマップで示される特徴に対する反応の強さをこのページでは暫定的に特徴強度と呼ぶ)。…
CIFAR-10
CIFAR-10 は 10 種に分類された 32×32 の 60,000 画像からなるデータセット。80 Million Tiny Images から画像認識のために抽出/分類したサブセットである。
Keras: ImageDataGenerator
Keras 2.2 に付属するデータ拡張と正規化のための多機能前処理ユーティリティ ImageDataGenerator のパラメータごとの効果を整理する。明文化されていない部分については Github のソースを参照する必要がある。
Keras: CNN画像分類 (転移学習/Fine Tuning)
転移学習 (transfer learning) はネットワークをゼロから学習させる代わりに、別のタスクで学習したネットワークを元に目的のタスクに最学習させることで、学習のための計算コストや学習に必要なデータセットの数を削減する手法。その際に行われる再学習は fine tuning (微調整) と呼ばれる。…
Keras: CNN画像分類 (Pre-trained CNN Model)
CNN モデルを使用した画像分類スクリプトを作成する。Keras は自分でニューラルネットワークを組み立てデータセットを用意してモデルを構築することもできるが、過去のコンペで優秀な成績を収めたいくつかの CNN がすぐに利用可能な形で含まれていて、推測部分にフォーカスして試すのであればそれらを利用するのが早い。…
Keras: ImageNet分類ラベル一覧
ImageNet データセットに基づく Keras 2.2.0 で利用可能な CNN 学習済みモデルの分類ラベルとその意味 (./keras/models/imagenet_class_index.json に保存されている)。サムネールは該当するラベルに分類されている画像を ImageNet からいくつかサンプリングしたもの。…
Lucene: 類似画像検索
AKAZE, ORB, SIFT, SURF などを使用して画像から特徴点とスケール・回転・輝度・Blur 耐性を持つ特徴量を抽出し、それらから Bug of Visual Words (Bag of Features) を使用して全文検索エンジンである Lucene
JavaVM 仕様読書会ノート
The Java® Virtual Machine Specification Java SE 10 Edition 読書会のノート。Connpass イベント。
認知バイアス
意思決定において根拠の一つ一つを吟味し合理的な判断を下すコストは決して低いものではない。人は重要ではない判断に対して、過去に経験したり記憶から導き出しやすい材料に基づいて意思決定を行っている。例えばシェフが 1 コース分の料理を作り上げるまでに、プログラマが 1 つのソースファイルを書き上げるまでに、小説家が 1 ページ分を書き上げるまでに数百から数千もの軽微な判断が行われている。…
TensorFlow + Keras セットアップ
OpenCV: 局所特徴量による類似画像検索/分類
画像の局所特徴量は回転や拡大縮小によって分布が変換しない特徴ベクトルである。つまり特徴量の分布の形が似ている画像は特徴点の配置が似ている画像であることが予想される。この局所特徴量を \(n\) 次元空間上でクラスタ化し、画像ごとに算出した Bag of Visual Words (Bag of Features とも) を使用して画像の類似度を得ることで、撮影されている物体の特徴に基づいた画像検索を行うことを目的とする。…
OpenCV: セットアップ
Windows / Java 環境で OpenCV を使うまでのセットアップ手順。OpenCV の Java バインディングは JAR ファイルとその JNI のネイティブライブラリ (Windows であれば DLL) の 2 ファイルで構成されている。これらをプロジェクトに追加してやれば良い。…
OpenCV: 特徴点/特徴量の抽出
Julia: 目的別機能
判断の選好逆転
完全に合理的な判断ができているのであれば前提条件が変わらない限り判断が変わることはない。しかし人は問題のとらえ方に流されて異なる判断を行いがちである。
OpenCV: 目的別機能
Julia: グラフの描画
PyPlot はプロットライブラリである matplotlib.python のインターフェースを Julia から使えるようにしたパッケージ。ローカルに導入する場合は REPL で PyPlot パッケージを導入しておく。
OpenCV 3
画像収集
機械学習を行う目的で対象物の画像を収集する方法について現時点での手順をまとめておく。処理は大まかに以下のステップを想定しているが:
ボロノイ領域
ボロノイ領域 (Volonoi region) は
意思決定
最大エントロピー法
最大エントロピー法 (maximum entropy model) は前提条件だけで明確な確率分布を導き出せない事象に対して、全体のエントロピーが最大化する方向に確率分布を割り当てる方法。条件が設定されていないのであれば、条件外の余計な偏りを含まない最も不確かなモデルが採用されるべきという考え方に基づく。…
論文翻訳: A Simple Introduction to Maximum Entropy Models for Natural Language Processing
自然言語処理における多くの問題は、言語学的文脈を用いて言語学的クラスを予測する言語学的分類問題と考えることができる。最大エントロピーモデルは特定の言語学的コンテキストで発生する特定の言語学的クラスの確率を推定するために、様々な文脈的根拠を組み合わせるクリーンな方法を提供する。このレポートでは例問題で特定の最大エントロピーモデルを使用して、そのモデルに関するいくつかの関連する数学的事実を簡単かつアクセス可能な方法で証明する。…
The Rust Programming Language ノート
The Rust Programming Language 2nd ED. からのメモ書き。
Rust 開発環境
S2 Geometry Library
S2 Geometry Library は球面上の領域を扱うための空間インデクシング (spatial indexing) ライブラリ。主に地球を対象としており、地理データを分割統治や索引付けのためのセル (区画) に分割することを目的としている。また非常にコンパクトで 64bit 整数で地球表面上の 1cm 四方を表す解像度を持つ。…
B+Tree
B-Tree の派生型である B+Tree は、個々のキーの検索効率を下げる代わりに、ある範囲のデータをまとめて取得するケース (レンジクエリー) に適した構造を持つ。B-Tree が中間ノードにもデータエントリを保持していたのに対して、B+Tree では末端の葉にのみエントリを保持し、葉は相互にリンクしたリストの構造を持っている。…
R-Tree
R-Tree は深さ平衡木 (depth-balanced tree)。葉ノード
論文翻訳: The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree
空間インデックス (spatial index) のためのアルゴリズム Priority R-Tree (2004) に関する論文。
論文翻訳: From Word Embeddings To Document Distances
我々はテキスト文書間の新しい距離関数である Word Mover's Distance (WMD) を提示する。我々の研究は文中の局所的な共起から単語の意味的に重要な表現を学習する単語埋め込み (word embedding) の最近の研究結果に基づいている。WMD 距離は、2 つのテキスト文書間の非類似度を、一方の文書に埋め込まれた単語が別の文書に埋め込まれた単語に到達するまでに「移動」する必要がある最小の距離量として算出する。…
論文翻訳: PositionRank: An Unsupervised Approach to Keyphrase Extraction from Scholarly Documents
学術論文からキーフレーズを抽出するためのアルゴリズム PositionRank (2017) に関する論文。
可変長整数エンコーディング
いくつかの可変長整数エンコーディング実装について。このページの話題は任意精度整数演算ではなくデータ圧縮の目的で整数値をエンコーディングする方法である。
社会心理学
React
React は SPA (Single Page Application) を開発するためのフレームワーク。JSX を含む JavaScript ソースやその依存ファイルをブラウザが解釈可能な形式にトランスコンパイルし、最終的に一般的な HTTP サーバにデプロイできる形の静的なファイルセットを作成する。…
英語ノート
英語のフレーズなどを記述しておくノート。
npm
npm (Node package manager) は JavaScript 用のパッケージマネージャで世界最大級のソフトウェアレジストリ。JavaScript 実行環境である Node.js のデフォルトのパッケージマネージャとして使用されている。公開されている再利用可能なコードを検索したり、それらをダウンロードしプロジェクトで利用することができる。…
Node.js セットアップ
Docker セットアップ
最小経路問題
重み付きグラフ上のある頂点 \(s\) から別の頂点 \(t\) まで到達する経路の中で最もコストの低い経路を求める問題 (重みなしグラフの場合は各辺の重みを 1 とする)。最小シュタイナー木問題において 2 点を使った最小コストの部分グラフを作成することと同じ。
最小全域木問題
いくつかの頂点と、各頂点の間をつなげるコスト (辺の重み) が定義されており、最も小さいコストですべての頂点をつなぐ最適化問題。コストは 0 より大きく接続不能 (つまりコスト \(\infty\)) も取り得る。すべての頂点がつながることから連結グラフでなければならず、また閉路はいずれか 1 本分の辺のコストが無駄であることから存在しない。…
タグ抽出
タグ抽出 (tag extraction) またはキーワード抽出の目的は文書の内容を代表していると思われる単語を選択する処理。他に自然文の構文構造を素性として重み付けする方法などいくつか過去の研究ある。
グラフ理論 序説
グラフ理論 (graph theory) は数学的概念であるグラフを説明する理論。問題を頂点と辺からなるグラフに抽象化し、その離散構造そのものを論議の対象とする。
論文翻訳: The Use of MMR, Diversity-Based Reranking for Reordering Documents and Producing Summaries
本稿はテキスト検索と要約の文脈において情報関連性とクエリー関連性を統合する方法を提示する。Maximal Marginal Relevance (MMR) の判定基準は、検索された文書の順位を変更したり、テキスト要約のための適切な一節を選択する際に、クエリーの関連性を維持しながら冗長性を減らすことを目的としている。…
コサイン類似度
ベクトル空間モデル (vector space model)、または単語ベクトルモデル (term vector model) はテキスト文書やそれに類似する任意のオブジェクトを識別子のベクトルとして表現するための代数空間モデルである。ここで識別子とは索引として使用できる n-gram や形態素ような情報を指している。…
論文翻訳: LexRank: Graph-based Lexical Centrality as Salience in Text Summarization
我々は推計学的な graph-based のグラフに基づいて自然言語処理におけるテキスト単位の相対的重要度を算出する方法を導入し、テキスト要約 (TS; text summarization) 問題でこの手法をテストする。抽出型要約 (extractive TS) は文書または文書セット内のもっとも重要な文を識別する要点文の概念に依る。…
自動要約
自動要約 (auto summarization) または文書要約は文書の要約を作成することを目的としたテキスト短縮の処理。対象とする文書が一つの場合を単一文書要約、特定の文書セットを要約する場合を複数文書要約と呼ぶ。単一文書要約は一般的に長い文章から重要な部分のみを取り出すことを目的とする。…
論文翻訳: TextRank: Bringing Order into Texts
この論文ではテキスト処理において graph-based ランキングモデルである TextRank を導入し、このモデルが自然言語アプリケーションにおいて有効に機能するかを示す。特に、キーワード抽出と文抽出の 2 つの革新的な教師なし学習の方法を提案し、得られた結果が既存のベンチマークで過去に公表された結果と適合することを示す。…
Holt-Winters 法
ホルト-ウィンターズ法 (Holt-Winters method) は指数平滑化法における時系列の変動にトレンドと季節変動を追加し、それぞれの指数平滑の重ね合わせを期待値として算出する方法。このため 3 重指数平滑化法 (triple exponential smoothing) とも呼ばれる。…
行動経済学
指数平滑化法
指数平滑化法 (exponential smoothing) は時系列データを平滑化する代表的な時系列分析手法。観測値の中でより新しいデータに大きな重みを設定し、過去になるほど指数関数的に重みを減少させた期待値 (移動平均) を算出する。直近の観測値の変動に従属させたいような比較的短期間の期待値を決めるのに適している。…
Julia 言語の特徴
Jupyter Notebook
Jupyter Notebook はライブコード、方程式、視覚化、テキストを含むドキュメントを作成して共有できるオープンソースの Web アプリケーション。データのクリーニングと変換、数値シミュレーション、統計モデリング、データの視覚化、機械学習などを目的として使用される。
Chainer セットアップ
Chainer はニューラルネットワークを記述するためのフレームワーク。既存の命令型フレームワークよりも "Define and Run" で柔軟性を重視しており宣言的にネットワークを記述することができる。
Python 3 セットアップ
この記述では Python 3 を使用して virtualenv で環境を切り替え pip でライブラリの管理を行うことをゴールとする。
MXNet セットアップ
Apache MXNet は高速でスケーラブルな機械学習フレームワーク。Gluon という高レベル API が付属しており AWS が正式にサポートしている。
メタプログラミング - Julia
Julia はコードを AST (abstract syntax tree; 抽象構文木) として評価する機能を持っている。ここでの評価とはコード上に AST を展開し実行することを意味する。このようなコード展開による評価は、強固なコンテキスト分離を持つ関数の呼び出しなどと異なり、実行コンテキストに強く影響する (黒魔術的な) 機能を実装することができる。…
多層パーセプトロン
多層パーセプトロン (MLP; multilayer perceptron) または Feedforward Neural Network, Deep Feedforward Network は典型的な深層機械学習のためのネットワークモデル。多層パーセプトロンはある関数 \(f\) の近似を目的とし、写像 \(\vector{y} = f(\vector{x}; \vector{\theta})\) が最良の近似関数となるようなパラメータ \(\vector{\theta}\) を学習する。…
Recurrent Neural Network
Recurrent Neural Network (RNN; 再帰型ニューラルネットワーク) は時系列の情報パターンを認識するように設計されたニューラルネットワーク。自然言語処理、遺伝子、センサーデータ、株式など、データのシーケンスを節に分解して時系列として扱うことができるデータを対象としている。…
React Native
React Native
Google Fusion Tables
Google Fusion Tables は Google が提供するデータベース。
Fusion Tables Client for Java/Scala
Java やその他の JavaVM 言語は Maven, Gradle, sbt などのビルドツールを利用して Maven リポジトリの Fusion Tables API のクライアントライブラリを利用するのが早いだろう。
MXBean
Service Worker
Service Worker の目的の一つはキャッシュ制御によるサイトの高速化である。ブラウザのキャッシュをサイト実装者が詳細に制御することで、動的に変化しないコンテンツ (HTML, CSS, JS, 画像等) をデバイスローカルにキャッシュし Web アプリケーションの表示を高速化する。…
Service Worker
Service Worker はブラウザネイティブと同じ UI でユーザに通知を行うことができる。通知方法には 2 種類あり、ユーザがアプリを起動していないときでもローカルで起動しているアプリからユーザに通知を行う方法。もうひとつがサーバから通知を受ける方法である。
Service Worker
Service Worker
サービスワーカー (service worker) はクライアント (ブラウザ) のバックグランドで実行される JavaScript 処理。HTML を操作するユーザインターフェースのスクリプトとは別のコンテキストで動作する。現在のところブラウザでのバックグラウンド同期、キャッシュ制御、ユーザ通知などを目的とした仕様策定と実装が進められている。…
Getting Started with Progressive Web Apps
Progressive Web Apps (PWA) は Google が開発したスマートフォン/タブレット向けのアプリケーションアーキテクチャ。HTML, JavaScript, CSS で作成できる。
メルカトル図法
メルカトル図法 (Mercator projection) またはメルカトル投影は円筒投影法を用いて球体表面の 2 次元座標を \(x\),\(y\) 座標の平面に投影する方法。ここでは地球上の地理の投影について述べている。
Latent Dirichlet Allocation
Note: ビットコインのブロックチェーン
BCCC 2017 で行った bitcon のブロックチェーン技術に関するノート。
制御構文
データ型
タイムゾーン一覧
TimeZone で定義されている通貨の一覧。
文字セット一覧
Charset に定義されている文字セット。
通貨一覧
Currency で定義されている通貨の一覧。
ロケール一覧
Locale で定義されている通貨の一覧。
システムプロパティ一覧
System で定義されている通貨の一覧。
ポアソン分布
単位時間あたりに平均 \(\mu\) 回観測される事象が、単位時間あたりに \(r\) 回観測される確率はポアソン分布 (poison distribution) に従う。\( P(X=r) = \frac{e^{-\lambda} \lambda^r}{r!}, \ \ r=0,1,\ldots\s \)
文字列の操作
数値の操作
Julia - 演算子
Julia の特徴的な演算子機能としては、べき乗と逆除算が用意されていること、そして言語機能のレベルで演算子のベクトル化が可能であることが挙げられる。C/C++ や Java などの言語知識があれば多くは読み飛ばしてもかまわない。
データ型・変数・関数
スクラップブック
相関係数
相関係数 (correlation coefficient) は確率変数 \(X\) に対する別の確率変数 \(Y\) の線形従属性を示す尺度。最も一般的なものは線形相関係数 (linear correlation coefficient) で積率相関係数 (product-moment correlation coefficient)、Peason の \(r\) (Pearson's r) とも呼ばれる。…
有効数字
有効数字 (significant figures of number) は実数の分解能を意味する数字。数値のどの桁までが意味を持つかを表している。
機械イプシロン
機械イプシロン (machine epsilon) は浮動小数点演算の丸めによって発生する相対誤差の上限を意味する。これはコンピュータ演算を使った数値解析特有のトピックである。macheps, unit roundoff または計算機イプシロンとも呼ばれ記号 \(\epsilon\), \({\bf u}\) で表される。…
TF-IDF
TF-IDF (term frequency - inverse document frequency) はある単語がコーパス内の文書に対してどれほど重要であるかを示す統計的数値。TF-IDF 値は文書内に単語が出現する回数に比例して増加するが、コーパス内での単語の出現頻度によって相殺されることが多く、一般に頻繁に出現する単語を調整する利点をもつ。…
形態素解析
自然言語処理ではよく単語を文章を構成する「意味を持つ情報」の最小単位として扱っている。ラテン語圏の言語は単語の区切りに空白を使用しているためプログラムでの抽出は比較的容易だが、日本語の場合は文の中から単語を識別し適切に分割する実装が必要となる。このような単語分割処理は対象とする言語圏ごとに実装する必要がある。…
疑似乱数サンプリング
疑似乱数サンプリング (pseudo-random number sampling) は与えられた確率分布に従う擬似乱数を生成する数値的手法。一般に一様乱数 \(u\) を利用して一様ではない分布のサンプリングを行う。
マルコフ連鎖
時刻やステップの推移で状態空間 \(\{1, 2, \ldots, k\}\) のいずれかの値を持つ確率変数について考える。ある時点 \(t\in(0, 1, \ldots)\) での確率変数を \(x^{(t)}\) とする。
マルコフ連鎖モンテカルロ法
マルコフ連鎖モンテカルロ法 (Markov chain Monte Carlo methods; MCMC 法) は確率分布から疑似乱数サンプリングを行うためのアルゴリズム。ある時点の状態 \(x^{(t)}\) からランダムに採択した次の状態 \(x^{(t+1)}\) へ確率付きで移動することから "マルコフ連鎖", "モンテカルロ法" の名前で呼ばれる。…
ベータ分布
ベータ分布 (beta distribution) は以下の式で表される連続確率分布。確率変数は \(0 \lt x \lt 1\) の範囲を取る。\( P(x; \alpha, \beta) = \frac{x^{\alpha-1}(1-x)^{\beta-1}}{B(\alpha,\beta)}, \,\,\, \alpha \gt 0, \beta\gt 0 \) ここで \(B(\alpha,\beta)\) はベータ関数である。…
不動点反復法
集合 \(X\) からそれ自身への写像 \(f\) が与えられたとき、\(f(x)=x\) を満たす元 \(x\) を不動点 (fixed-point) または固定点と言う。グラフ上では、連続関数 \(f:\mathbb{R} \Rightarrow \mathbb{R}\) の不動点は曲線 \(y=f(x)\) と対角線 \(y=x\) の交点の \(x\) 座標である。…
モンティ・ホール問題
1990 年に話題になったとき、著名な数学者を含む多くの人が「同じ確率だから選択を変える必要はない」と答えた問題。最終的な状況を客観視すると、選択可能な箱が 2 つあってそのうちのどちらかが当たりであることから、どちらを選んでも確率は 1/2 に思える。司会者がハズレの箱を間引いたところで当たりの箱は何も影響を受けていないので確率が 1/3 から 1/2 に変化しただけだろう、ということだ。…
ベルヌーイ分布
結果が {0, 1}、{true, false}、{OK, NG} といった 2 値しかとりえない独立した事象の試みをベルヌーイ試行 (bernoulli trial) と呼ぶ。これらの結果は統計で扱う便宜上 \(b \in \{0,1\}\) に置き換えて考える。
カテゴリカル分布
それぞれ独立した確率 \(p_k\) を持つ \(K\) 個の事象 (カテゴリカル変数; categorical variable) が存在し、1 回の独立した試行でそのいずれか一つが観測される離散確率分布をカテゴリカル分布 (categorical distribution) と呼ぶ。…
カイ二乗分布
\(\vector{x} = (x_1, x_2, \cdots, x_k)\) が標準正規分布に従う確率変数であるとき、その自乗和 \( Z = \sum_{i=1}^k x_i^2 \) は自由度 \(k\) のカイ二乗分布に従う (\(\chi_k^2\) と表す)。確率密度関数は \( f(z;k) = \frac{e^{-\frac{1}{2}z}z^{\frac{1}{2}k-1}}{2^{\frac{1}{2}k}\Gamma(\frac{1}{2}k)}, z \gt 0 \) 平均 \(k\)、分散 \(2k\)、最頻値は \(k \leq 2\) のとき 0 となりそれ以外では \(k-2\)。…
多項分布の推定
事象 \(k \in \{1,2,\cdots,K\}\) がそれぞれ生起確率 \(\vector{p} = (p_1,p_2,\cdots,p_K)\) に従って観測されるとき、標本 \(x=k\) が観測される確率 \(P(k)=p_k\) の分布はカテゴリカル分布に従う。さらにカテゴリカル分布に従う試行を \(n\) 回行ったとき、それぞれの事象の観測数を \(\vector{x} = (x_1, x_2, \cdots, x_K)\) とすると、ある標本 \(\vector{x}\) が観測される確率分布は多項分布 (\(\ref{multinomial_distribution}\)) に従う。…
二項分布
試行において 1 が観測される確率 \(p\) のベルヌーイ試行を \(n\) 回行ったとき (あるいは \(n\) 個同時に行ったとき) に 1 が \(x\) 個観測される確率は \(p\) と \(n\) をパラメータとした以下の確率質量関数で表される。\( P(x; n,p) = \binom nx p^{x} (1-p)^{n-x} \) ここで二項係数は以下のように表される。…
多項分布
独立した \(K\) 個の事象 \(k \in \{1, 2, \ldots, K\}\) のいずれか一つが観測される確率をそれぞれ \(\vector{p} = (p_1, p_2, \ldots, p_K)\) とする。この試行を \(n\) 回繰り返したときに各事象の観測された回数を確率変数 \(x_k\) とする。…
浮動小数点数
浮動小数点演算 (floating-point arithmetic) は実数をある範囲の精度で近似した数式表現で行う算術演算のこと。この近似表現を浮動小数点数という。科学技術計算では非常に大きな値や小さな値を扱う代わりに、観測精度の限界から必要な有効数字が保証されていれば十分であることが多い。…
高速逆二乗根
高速逆二乗根 (fast inverse square root) は浮動小数点と定数を用いて \(\frac{1}{\sqrt{x}}\) を高速に演算する方法。
Numerical Algorithms for Scala
学生の頃に Numerical Recipes in C という多くの実数演算アルゴリズムの載った書籍があった。英語版は 3rd Ed. が出ているようだが日本語版は出ていない。アルゴリズム辞典や数値演算ライブラリを作る気はないのだが系統としてはあの本の方向で行ければ良いと思っている。…
正規分布の推定
平均 \(\mu\)、分散 \(\sigma^2\) をパラメータとする正規分布 \({\rm Norm}(\mu,\sigma^2)\) にもとづいて確率変数 \(x\) が観測されるとき、その確率密度関数は以下のように表される。\( P(x|\mu,\sigma^2) = \frac{1}{\sqrt{2\pi\sigma^2}} {\rm exp}\left\{-\frac{(x-\mu)^2}{2\sigma^2}\right\} \)
二項分布の推定
事象 \(b \in \{0,1\}\) のベルヌーイ試行で \(b=1\) となる確率を \(p\)、試行回数を \(n\) とした時、1 が \(x\) 回観測される (出た数の合計が \(x\) となる) 確率関数は二項分布 \(P(x;n,p)\) に従う。ここで \(x=k\) となる確率は以下のように表される。…
ND4J ユーザガイド
最尤推定とMAP推定
ある生起確率 \(\vector{\theta}=(\theta_1, \ldots, \theta_N)\) に基づいてデータ \(\vector{X} = (x_1, x_2, \ldots, x_N)\) が観測されるとき、あるデータ \(\vector{X}\) が観測される確率は \(\vector{p}(\vector{X}|\vector{\theta})\) で表される (条件付き確率)。…
ベータ関数
ベータ関数 (beta function) は以下の積分で定義される特殊関数。\( B(x, y) = B(y, x) = \int_0^1 t^{x-1} (1-t)^{y-1} dt \) またガンマ関数を使用して以下のように表すこともできる。\( \begin{equation} B(x, y) = \frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)} \label{beta_expressed_gamma} \end{equation} \) したがって \(x\) と \(y\) が正の整数であれば階乗として表すことができる。…
ガンマ関数と階乗
ガンマ関数 (gamma function) は 0 または負の整数以外の複素数に対して以下の積分で定義される特殊関数。\( \Gamma(z) = \int_0^\infty t^{z-1} e^{-t} dt \) また漸化式 \(\Gamma(z+1) = z \Gamma(z)\) でも表すことができる。…
ラグランジュの未定乗数法
ラグランジュの未定乗数法 (method of Lagrange multiplier) は制約付き最適化問題で極値を求めるための手法である。ある 1 つ以上の条件 \(g(x)=0\) の下で関数 \(f(x)\) が最大値/最小値を取ることを式 (\(\ref{optimal_consumption}\)) のように表す。…
ディリクレ分布
ディリクレ分布 (dirichlet distribution) は独立した事象 \(k \in \{1, 2, \cdots, K\}\) がそれぞれ \(x_k=\alpha_k - 1\) 回観測されたときに各事象の生起確率が \(p_k\) である確率を示す連続した確率密度関数。…
usb4j の機能
usb4j は USB デバイスと通信する Java アプリケーションを開発するためのライブラリです。Java の高い移植性を生かしてプラットフォームごとに異なる USB 実装をより抽象化した API で利用することを目的としています。
USB for Java
USB for Java
USB for Java は Java から USB デバイスと通信するためのライブラリです。
HTTP Sniffer Proxy
Java 製のプロキシ型 HTTP リクエスト/レスポンス Sniffer。クライアントから想定通りのリクエストが出ているか、サーバがきちんと Cookie を返しているかなど、ブラウザのソース表示だけでは分からない通信プロトコルを調査する Web ディベロッパー向けツールです。…
2. プロトコル層
3. 物理プロトコル
7. データ型
Garmin Device Interface Specification
6. アプリケーションプロトコル
5. アプリケーションプロトコルの概要
1. 導入
4. リンクプロトコル
SWT レイアウトマネージャ
SWT は AWT とは別に専用のレイアウトマネージャを用意していますが、機能や役割は AWT のそれと同じです。
Standard Widget Toolkit
SWT (Standard Widget Toolkit) は IBM が Eclipse 用に開発した GUI ライブラリです。JNI を使用することで昔の Swing で問題となっていたグラフィック描画のボトルネックを回避し、当時の Swing ベースのアプリケーションと比較して格段の速さを誇っていました。…
Secure Sockets Layer
SSL (secure sockets layer) は公開鍵暗号と共通鍵暗号、電子署名、公開鍵証明書などの技術を組み合わせ、暗号化による盗聴防止、改ざん・破損の検出、通信相手の証明などを一度に実現している通信技術。
共通鍵暗号
公開鍵暗号 入門
異なる鍵 A と B が存在した場合、A で暗号化したデータが B でしか復号化できないといった特殊な鍵の組み合わせを非対称鍵 (asymmetric key) と言う。公開鍵暗号 (public-key encryption) は非対称鍵の特性を利用して鍵の片方を暗号化用に相手に公開し (公開鍵)、もう片方を復号化用に非公開にしておく (秘密鍵) 方式。…
Java GUI
現在 Java で利用されている主な GUI (Graphical User Interface) ライブラリは AWT、Swing、SWT の 3 つです。ただし AWT のみによる GUI アプリケーション開発は既にほとんど行われておりません。
電子署名
電子署名 (digital signature) は文書に対する承認と、文書内容の保障を電子的に付け加えるための暗号技術。公開鍵を使用することにより他人によって行われた署名でないことと、署名された時点から文書内容に変更がないことの 2 点を証明することができる。また電子署名法により 2001 年から電子商取引などにおける法的根拠としても利用可能となっている。…
Swing
Swing はプラットフォーム依存のウィジェットに頼らず、全てのコンポーネント描画と状態の管理を Java で実装した GUI ライブラリです。元々 AWT の機能の薄さを補うために Sun が Netscape 社 (当時) と共同で開発した Java Foundation Class (JFC) という GUI ライブラリが J2SE 1.2 から標準となりました。…
Abstract Window Toolkit
AWT (Abstract Window Toolkit) は初期の Java で標準として用意されていた GUI ライブラリです。それまでプラットフォームごとに使い方が異なっていたウィジェット (GUI コンポーネント) を抽象化し、Java から統一した標準 API として使用できるようにしています。…
Jython
Jython は動的オブジェクト指向スクリプト言語 Python の Java 実装版です。java.net スクリプトプロジェクトの一つとしてとして開発が進められています。
システムトレイ
Java SE 6 からシステムトレイ (タスクトレイ) が利用できるようになりました。メール着信のお知らせツール (biff) やウィンドウレスで常駐するアプリケーションで便利な機能です。この機能は Windows, Macintosh, GNOME, KDE など、デスクトップ用途を前提としたウィンドウマネージャであれば大抵は利用可能です。…
Rhino
Rhino は元々 Mozilla プロジェクトで開発されていた Pure Java 製の JavaScript (ECMAScript) エンジンです。JDK 1.1 からの長い歴史を持ち (そして一時期の暗黒時代を経て)、Java SE 6 の Scripting API 実装として標準バンドルされています。…
Google Fusion Tables
Berkeley DB はカリフォルニア大バークレイ校で開発されたデータベースライブラリ。データベースと言っても RDBMS のように SQL が使用できたり関連モデルで設計されているわけではなく、ファイル上にインデックス付けされたデータ構造をプロシジャ形式のインターフェースを用いて検索、更新出来るライブラリ (Database Manager) です。…
Solaris 10 for x86 インストール
Solaris 10 8/07 for x86 のダウンロードから起動までの手順を解説する。なお作業は VMWare のゲスト OS として行っているため通常のインストールと異なる部分が若干あるかもしれない。
Solaris 10 セットアップ
導入直後の root ユーザのホームディレクトリは / に設定されているがセキュリティ面でも運用面でもろしくないので変更する。
Scripting for the Java™ Platform
Scripting for the Java™ Platform は JSR 223 で標準化され Java SE 6 から導入されたスクリプト API。文字列や外部ファイルに記述されているスクリプトを Java 上で実行することができる。
GIF 画像出力
米 Unisys 社が取得していた GIF の LZW 圧縮に関する特許が2004年6月20日に切れ Java SE 6 から GIF への出力がサポートされた。このページでは Java SE 6 の Image I/O を使用してアニメーション GIF を作成する方法について述べる。…