makenowjust-labs/blog

MakeNowJust Laboratory Tech Blog

記事

JavaScript のソースコードを (意地でも) 小さくする技術

2022-03-21

JavaScript のソースコードを小さくする方法として UglifyJSTerser といった minification ツールを用いるものが良く知られています。 これらはソースコード中の空白やコメントを削除し、変数名などを短い形式にすることで、ソースコードを小さくしています。

こういった minification ツールを適用し、さらに GZip などで圧縮して配信するのが今日の Web での標準的な方法となっています。 ですが、JavaScript を圧縮できる可能性のある方法として、自己解凍的な圧縮技術を用いる、というアイディアがあります。

この記事では、そういった自己解凍的な圧縮技術として JS CrushRoadroller について紹介します。

ブログを Next.js へ移行しました

2022-03-11

元々は GatsbyJS で作られていたこのブログを、Next.js で書き直して復活させました。 放置している間にもいくつか記事にしたい事柄があったのですが、元の仕組みでは記事を書く気が起きず、結果的に 1 年近く放置することになってしまいました。

この記事では「なぜ GatsbyJS から移行したのか」と「他のフレームワークを比較した結果」、そして「最終的な技術スタック」について説明します。

Hopcroft のアルゴリズムについて

2021-04-02

前回の記事では DFA 最小化アルゴリズムとして Brzozowski のアルゴリズムを解説しました。 今回は、別の最小化アルゴリズムとして Hopcroft のアルゴリズムについて解説します。

"Introduction to Automata Theory, Languages, and Computation" (日本語訳『オートマトン 言語理論 計算論』) の著者の一人として知られる John Hopcroft が 1971 年に発表したアルゴリズムです。 実装を工夫することで最悪計算量は DFA の状態数 nn に対して O(nlogn)O(n \log n) となることが知られています。 しかし、正当さがやや直感的でないことから、オートマトン理論の教科書や講義などで触れられる機会は少ないように思います。

この記事では、Hopcroft のアルゴリズムの実装に加えて、その正しさの証明や計算量の解析を行います。

Brzozowski のアルゴリズムとは結局何なのか

2021-03-19 (更新: 2021-03-21)

AA を言語 LL を受理する DFA とすると、D(R(D(R(A))))D(R(D(R(A)))) は言語 LL を受理する最小 DFA となります。 ここで D(A)D(A) というのは部分集合構成法による決定化の処理で、R(A)R(A) は DFA の各遷移と初期状態・受理状態を反対にして NFA を求める処理を表します。 この 2 回のリバースと決定化を行う DFA の最小化アルゴリズムは Brozozowski のアルゴリズム として知られています。 Brzozowski 微分などで知られる Janusz Brzozowski が 1960 年代に発表したアルゴリズムです。

以前 Qiita でこのアルゴリズムでどうして DFA の最小化が行なえるのかを説明したのですが(Brzozowski のアルゴリズム - なぜ DFA を 2 回反転すると最小化できるのか )、これによって構成される DFA がどのようなものなのかは説明していませんでした。 今回のこの記事では、Brozozowski のアルゴリズムで求まる最小 DFA がどのようなものなのかを別の角度から少し解説したいと思います。