HOWTO · Java

Java でのデータ構造のトライ

このチュートリアルでは、Java の Trie データ構造について説明します。

著者 Sheeraz Gul公開日 2023-06-20更新日 2024-02-15

このチュートリアルでは、Java の Trie データ構造について説明します。

Java でのデータ構造のトライ

トライワードは、単語の検索から抽出されます。これは、一連の文字列を格納するために使用される並べ替えられたデータ構造です。 Trie は、各ノードの文字数に等しい数のポインターを持つデータ構造として定義できます。

単語のプレフィックスを利用して、Trie データ構造を使用して辞書から単語を検索できます。このシナリオでは、辞書内のすべての単語が 26 個の英語のアルファベットから作成されている場合、各 Trie ノードには 26 個のポイントがあります。

トライデータ構造は、プレフィックスツリーまたはデジタルツリーとも呼ばれ、ノードの位置によって、ノードが接続されるキーが決まります。次の図から、Trie がどのように機能するかを理解してみましょう。

トライデータ構造 Java

上の図には、単語 deal、delft、および delete のツリー構造が含まれています。

Trie データ構造のプロパティ

文字列の Trie セットの主なプロパティは次のとおりです。

ルートノードは常にヌルノードです。
すべての子ノードがアルファベット順にソートされます。
英語のアルファベットのため、各ノードは 26 を超える子を持つことはできません。
すべてのノードは、アルファベットから 1 文字を格納できます。

トライデータ構造の応用

Trie データ構造の主な用途をいくつか見てみましょう。

Trie は、すべての文字が小文字であると想定する必要がある場合に使用できます。
ハイフンや句読点などを使用せずに、a-z の文字のみを使用する必要がある場合。
言葉の長さが限られている場合。たとえば、2x2 ボードで作業している場合、単語の長さは 4 を超えることはできないため、それらの単語は破棄できます。
辞書には、lawn と lawnmower など、同じ語幹を共有する単語が多数あります。トライは、これらの屈折語に使用できます。

トライデータ構造の基本操作

Trie には 3つの基本操作があります。

挿入操作

最初の操作は、ノードをトライに挿入することです。そのためには、次の点を理解する必要があります。

入力単語のすべての文字が個別にトライノードに挿入されます。
文字の長さによってトライの長さが決まります。
キー文字配列は、子のインデックスとして機能します。
現在のノードが現在の文字への参照を持っている場合、そのノードを参照した現在のノードを設定します。それ以外の場合は、新しいノードを作成する必要があります。

検索操作

Trie の 2 番目の基本操作は、ノードの検索です。この操作も挿入と同様です。

同じアプローチを使用してノードを検索するだけです。

削除操作

3 番目の操作は、ノードの削除です。これも簡単な操作です。

削除を開始する前に、次の 2つの点を考慮する必要があります。

検索中にノードキーが見つからない場合、削除操作は停止して終了します。
Trie の検索中にノードキーが見つかった場合、削除操作によってキーが削除されます。

Trie データ構造の Java 実装

小文字の a-z 英字のみをサポートする Trie データ構造を実装してみましょう。例を参照してください:

package delftstack;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Trie_Node {
  // 26 characters for a – z
  private static final int CHARACTER_SIZE = 26;

  private boolean Is_Leaf;
  private List<Trie_Node> Trie_Children = null;

  // Constructor
  Trie_Node() {
    Is_Leaf = false;
    Trie_Children = new ArrayList<>(Collections.nCopies(CHARACTER_SIZE, null));
  }

  // function for insertion
  public void Insertion(String Node_Key) {
    System.out.println("Inserting the key \"" + Node_Key + "\"");

    // root node
    Trie_Node root_node = this;

    // repeat for every character of the key
    for (char character : Node_Key.toCharArray()) {
      // create a new Trie node if the path does not exist
      if (root_node.Trie_Children.get(character - 'a') == null) {
        root_node.Trie_Children.set(character - 'a', new Trie_Node());
      }

      // going to the next node
      root_node = root_node.Trie_Children.get(character - 'a');
    }

    // current node as a leaf
    root_node.Is_Leaf = true;
  }

  // Method for search
  public boolean Searching(String Node_Key) {
    System.out.print("Searching the key \"" + Node_Key + "\" : ");

    Trie_Node Current_Node = this;

    // repeat for the character of the key
    for (char character : Node_Key.toCharArray()) {
      // going to the next node
      Current_Node = Current_Node.Trie_Children.get(character - 'a');

      // reach out to the end of a path in the Trie if the string is invalid
      if (Current_Node == null) {
        return false;
      }
    }
    return Current_Node.Is_Leaf;
  }
}

public class Example {
  public static void main(String[] args) {
    // construct a new Trie node
    Trie_Node New_Trie = new Trie_Node();

    New_Trie.Insertion("delft");
    New_Trie.Insertion("delf");
    New_Trie.Insertion("del");

    System.out.println(New_Trie.Searching("del")); // true
    System.out.println(New_Trie.Searching("delf")); // true
    System.out.println(New_Trie.Searching("delft")); // true
    System.out.println(New_Trie.Searching("delftstack")); // false

    New_Trie.Insertion("delftstack");

    System.out.println(New_Trie.Searching("del")); // true
    System.out.println(New_Trie.Searching("delf")); // true
    System.out.println(New_Trie.Searching("delft")); // true
    System.out.println(New_Trie.Searching("delftstack")); // true
  }
}

上記のコードは、Trie データ構造の挿入および検索操作を実装しています。出力を参照してください。

Inserting the key "delft"
Inserting the key "delf"
Inserting the key "del"
Searching the key "del" : true
Searching the key "delf" : true
Searching the key "delft" : true
Searching the key "delftstack" : false
Inserting the key "delftstack"
Searching the key "del" : true
Searching the key "delf" : true
Searching the key "delft" : true
Searching the key "delftstack" : true

ここで、Trie データ構造の空間複雑度は O(N × M × C) です。ここで、

N - 文字列の数
M - 文字列の最大長。
C - アルファベットのサイズ

そのため、上記のスペースの複雑さを持つ Java では、ストレージの問題が発生する可能性があります。

Java の HashMap を使用して Trie を実装し、ストレージの問題を解決することもできます。 HashMap を使用して Trie を実装してみましょう:

package delftstack;

import java.util.HashMap;
import java.util.Map;

class Trie_Node {
  private boolean Is_Leaf;
  private Map<Character, Trie_Node> Trie_Children;

  // Constructor
  Trie_Node() {
    Is_Leaf = false;
    Trie_Children = new HashMap<>();
  }

  // Insertion
  public void Insertion(String Node_Key) {
    System.out.println("Inserting the key \"" + Node_Key + "\"");

    // root node
    Trie_Node root_node = this;

    for (char character : Node_Key.toCharArray()) {
      // if the path doesn't exist, create a new node.
      root_node.Trie_Children.putIfAbsent(character, new Trie_Node());

      // going to the next node
      root_node = root_node.Trie_Children.get(character);
    }
    root_node.Is_Leaf = true;
  }
  // Searching
  public boolean Searching(String Node_key) {
    System.out.print("Searching the key \"" + Node_key + "\" : ");

    Trie_Node Current_Node = this;

    // repeat
    for (char character : Node_key.toCharArray()) {
      // going to the next node
      Current_Node = Current_Node.Trie_Children.get(character);

      if (Current_Node == null) {
        return false;
      }
    }

    return Current_Node.Is_Leaf;
  }
}

public class Example {
  public static void main(String[] args) {
    // construct a new Trie node
    Trie_Node New_Trie = new Trie_Node();

    New_Trie.Insertion("delft");
    New_Trie.Insertion("delf");
    New_Trie.Insertion("del");

    System.out.println(New_Trie.Searching("del")); // true
    System.out.println(New_Trie.Searching("delf")); // true
    System.out.println(New_Trie.Searching("delft")); // true
    System.out.println(New_Trie.Searching("delftstack")); // false

    New_Trie.Insertion("delftstack");

    System.out.println(New_Trie.Searching("del")); // true
    System.out.println(New_Trie.Searching("delf")); // true
    System.out.println(New_Trie.Searching("delft")); // true
    System.out.println(New_Trie.Searching("delftstack")); // true
  }
}

コードは同じ作業を行いますが、よりメモリ効率の良い方法で行います。 Java での Trie の出力を参照してください。

Inserting the key "delft"
Inserting the key "delf"
Inserting the key "del"
Searching the key "del" : true
Searching the key "delf" : true
Searching the key "delft" : true
Searching the key "delftstack" : false
Inserting the key "delftstack"
Searching the key "del" : true
Searching the key "delf" : true
Searching the key "delft" : true
Searching the key "delftstack" : true

著者について

Sheeraz Gul

Sheeraz is a Doctorate fellow in Computer Science at Northwestern Polytechnical University, Xian, China. He has 7 years of Software Development experience in AI, Web, Database, and Desktop technologies. He writes tutorials in Java, PHP, Python, GoLang, R, etc., to help beginners learn the field of Computer Science.

著者プロフィールを見る