アルゴリズムの設計において、各局面で局所的に最善の選択を行うことで、結果として大域的な最適解を目指すアプローチを「貪欲法（Greedy Algorithm）」と呼びます。この手法は計算コストが低く実装が比較的容易ですが、必ずしも全てのケースで最適解を保証するわけではありません。以下では、贪欲法を応用した代表的な 2 つの問題、すなわち物体の収容効率化とデータ圧縮の実装例について解説します。
1. 物体の効率的な収容問題（ビンパッキング問題の簡易版）
異なる体積を持つ複数の物品を、一定容量の容器に詰める際、使用する容器の総数を最小化する問題を考えます。具体的には、与えられた物品リストを順次処理し、現在使用中の容器に収容できる場合はそれに入れる、できない場合は新規の容器を開けるというロジックを採用します。
実装においては、動的配列を用いて利用可能な容器を管理し、各物品に対して最初の空き容量を満たす容器を検索します。見つからない場合に限り、新たなインスタンスを作成してリストへ追加します。
// 容器詰め最適化クラス
public class VolumeOptimizer {
/**
* 単一の容器を表す内部構造
*/
private static class StorageUnit {
private final int maxCapacity;
private int remainingSpace;
private List<Integer> containedItems;
public StorageUnit(int cap) {
this.maxCapacity = cap;
this.remainingSpace = cap;
this.containedItems = new ArrayList<>();
}
public void addItem(int volume) {
if (this.remainingSpace >= volume) {
this.remainingSpace -= volume;
this.containedItems.add(volume);
}
}
public boolean canFit(int volume) {
return this.remainingSpace >= volume;
}
}
/**
* 物品リストを容器に最適化して詰め込み、使用された容器リストを返す
* @param itemVolumes 詰め込む物品の体積リスト
* @param boxCapacity 一つの容器が持つ最大容量
* @return 配置済みの容器コレクション
*/
public List<StorageUnit> optimizePacking(List<Integer> itemVolumes, int boxCapacity) {
List<StorageUnit> activeBoxes = new ArrayList<>();
for (Integer currentItem : itemVolumes) {
if (currentItem > boxCapacity) {
throw new IllegalArgumentException("指定された物品は容器の限界を超えています");
}
// 既存の容器内で、この物品を受け入れられるものを探す（第 1 ヒット優先）
StorageUnit targetBox = null;
for (StorageUnit box : activeBoxes) {
if (box.canFit(currentItem)) {
targetBox = box;
break;
}
}
if (targetBox != null) {
// 既存の容器に詰める
targetBox.addItem(currentItem);
} else {
// 新しい容器を用意して詰める
StorageUnit newBox = new StorageUnit(boxCapacity);
newBox.addItem(currentItem);
activeBoxes.add(newBox);
}
}
return activeBoxes;
}
// メインエントリーポイントのテスト例
public static void main(String[] args) {
VolumeOptimizer optimizer = new VolumeOptimizer();
List<Integer> products = Arrays.asList(5, 4, 3, 2, 1, 4, 4, 2, 1);
int limitVolume = 5;
List<StorageUnit> result = optimizer.optimizePacking(products, limitVolume);
System.out.println("必要容器数：" + result.size());
for (StorageUnit u : result) {
System.out.println(u.containedItems);
}
}
}2. ハフマン符号化によるデータ圧縮
テキストデータを通信経路などで効率的に送信する場合、出現頻度の高い文字には短いビット列を割り当て、出現頻度の低い文字には長いビット列を割り当てる方式です。これにより、転送する全体のビット数を削減できます。ハフマン木と呼ばれるバイナリ木を構築し、木の深さに基づいて符号を決定します。
実装の手順は以下の通りです：
- 入力テキスト内の各文字種（またはトークン）の出現回数を集計する。
- 出現回数の小さい順序でノードを管理する優先度付きキューを使用し、木をボトムアップで構築する。
- 生成された木を走査し、左子なら"0"、右子なら"1"を追加していく形式で符号辞書を生成する。
- 元の文字列を符号辞書に従って変換し、復元用のルール情報も付加して出力する。
コード実装では、再帰処理と優先度付きキューを活用して木構造を管理します。
// データ圧縮エンジンクラス
public class BinaryCompressionEngine {
/**
* ハフマン木のノード
*/
private static class Node implements Comparable<Node> {
char data;
int frequency;
Node left;
Node right;
// リーフノード用
public Node(char d, int f) {
this.data = d;
this.frequency = f;
}
// 中間ノード用
public Node(int f, Node l, Node r) {
this.frequency = f;
this.left = l;
this.right = r;
}
@Override
public int compareTo(Node other) {
return Integer.compare(this.frequency, other.frequency);
}
}
/**
* 文字列内の各文字の頻度をマップに変換する
*/
private Map<Character, Integer> countFrequencies(String text) {
Map<Character, Integer> counts = new HashMap<>();
for (char c : text.toCharArray()) {
counts.put(c, counts.getOrDefault(c, 0) + 1);
}
return counts;
}
/**
* 頻度マップからハフマン木のルートノードを作成する
*/
private Node buildTree(Map<Character, Integer> frequencies) {
PriorityQueue<Node> queue = new PriorityQueue<>();
// すべての頻度をキューへ登録
for (Map.Entry<Character, Integer> entry : frequencies.entrySet()) {
queue.offer(new Node(entry.getKey(), entry.getValue()));
}
// ケース: 文字種が 1 つしかない場合
if (queue.size() == 1) {
Node single = queue.poll();
// 特別な処理が必要ない場合はそのまま返すが、木構造を保つためダミーの子を作ることが多い
return single;
}
while (queue.size() > 1) {
Node left = queue.poll();
Node right = queue.poll();
// 新しい親ノードを作成して再挿入
Node merged = new Node(left.frequency + right.frequency, left, right);
queue.offer(merged);
}
return queue.poll();
}
/**
* 生成された木から暗号字典（マッピング）を作成する
*/
private Map<Character, String> generateCodes(Node root) {
Map<Character, String> codes = new HashMap<>();
traverseTree(root, "", codes);
return codes;
}
private void traverseTree(Node node, String currentCode, Map<Character, String> codes) {
if (node == null) return;
// リーフノードの場合、現在のパスを記録
if (node.left == null && node.right == null) {
codes.put(node.data, currentCode.isEmpty() ? "0" : currentCode);
}
traverseTree(node.left, currentCode + "0", codes);
traverseTree(node.right, currentCode + "1", codes);
}
/**
* 文字列を圧縮形式（データ＋辞書の形式）に変換する
*/
public String compress(String originalText) {
if (originalText == null || originalText.isEmpty()) {
return "";
}
Map<Character, Integer> freqs = countFrequencies(originalText);
Node root = buildTree(freqs);
Map<Character, String> dictionary = generateCodes(root);
// 圧縮データのビルド
StringBuilder encodedBuffer = new StringBuilder();
for (char c : originalText.toCharArray()) {
encodedBuffer.append(dictionary.get(c));
}
// 復号に必要な規則（辞書）を生成
StringBuilder ruleBuilder = new StringBuilder();
for (Map.Entry<Character, String> entry : dictionary.entrySet()) {
ruleBuilder.append(entry.getKey()).append(":")
.append(entry.getValue()).append(";");
}
// データと規則を区切り文字で結合（ここでは'#'を使用）
return encodedBuffer.toString() + "#" + ruleBuilder.toString();
}
/**
* 圧縮データを元の文字列に戻す
*/
public String decompress(String compressedData) {
String[] parts = compressedData.split("#", -1);
if (parts.length != 2) {
throw new IllegalArgumentException("フォーマットエラー：圧縮データが見つかりません");
}
String binarySequence = parts[0];
String rulesRaw = parts[1];
// ルール情報のパース
Map<String, Character> decodeMap = new HashMap<>();
String[] pairs = rulesRaw.split(";");
for (String pair : pairs) {
if (pair.isEmpty()) continue;
String[] kv = pair.split(":");
// key は文字、value はコードなので逆引き辞書を作る
decodeMap.put(kv[1], kv[0].charAt(0));
}
StringBuilder result = new StringBuilder();
String currentBinary = "";
for (int i = 0; i < binarySequence.length(); i++) {
currentBinary += binarySequence.charAt(i);
if (decodeMap.containsKey(currentBinary)) {
result.append(decodeMap.get(currentBinary));
currentBinary = "";
}
}
return result.toString();
}
public static void main(String[] args) {
BinaryCompressionEngine engine = new BinaryCompressionEngine();
String testInput = "aababcabcd";
String packed = engine.compress(testInput);
System.out.println("圧縮後:" + packed);
String restored = engine.decompress(packed);
System.out.println("復元後:" + restored);
System.out.println("一致：" + testInput.equals(restored));
}
}