Implémentation des Arbres de Préfixe en Ruby

Les arbres de préfixe, également connus sous le nom de tries, sont des structures de données efficaces pour stocker et rechercher des chaînes de caractères. Ils sont particulièrement utiles pour des applications telles que l'autocomplétion, la recherche de mots et la gestion de dictionnaires. Dans cet article, nous allons explorer comment implémenter un arbre de préfixe en Ruby, en fournissant des exemples de code et des explications détaillées.

Qu'est-ce qu'un Arbre de Préfixe ?

Un arbre de préfixe est une structure de données arborescente où chaque nœud représente un caractère d'une chaîne. Les chemins de la racine à un nœud représentent les préfixes des chaînes stockées dans l'arbre. Voici quelques caractéristiques clés des arbres de préfixe :

Chaque nœud peut avoir plusieurs enfants, chacun représentant un caractère différent.
Les chaînes sont stockées de manière à ce que les préfixes communs soient partagés, ce qui économise de l'espace.
Les opérations de recherche, d'insertion et de suppression sont généralement très efficaces.

Pourquoi Utiliser un Arbre de Préfixe ?

Les arbres de préfixe offrent plusieurs avantages par rapport à d'autres structures de données, notamment :

Recherche rapide : La recherche d'une chaîne dans un arbre de préfixe est généralement O(m), où m est la longueur de la chaîne.
Économie d'espace : Les préfixes communs sont stockés une seule fois, ce qui réduit la redondance.
Fonctionnalités avancées : Ils permettent des opérations comme la recherche de mots par préfixe, ce qui est idéal pour les applications d'autocomplétion.

Implémentation d'un Arbre de Préfixe en Ruby

Voyons maintenant comment implémenter un arbre de préfixe en Ruby. Nous allons créer une classe Trie qui contiendra des nœuds et des méthodes pour insérer et rechercher des mots.

Création de la Classe Node

La première étape consiste à créer une classe pour représenter un nœud dans l'arbre. Chaque nœud aura un hash pour stocker ses enfants et un booléen pour indiquer si un mot se termine à ce nœud.

class Node
  attr_accessor :children, :is_end_of_word

  def initialize
    @children = {}
    @is_end_of_word = false
  end
end

Création de la Classe Trie

Ensuite, nous allons créer la classe Trie qui contiendra les méthodes pour insérer et rechercher des mots.

class Trie
  def initialize
    @root = Node.new
  end

  def insert(word)
    current_node = @root
    word.each_char do |char|
      current_node.children[char] ||= Node.new
      current_node = current_node.children[char]
    end
    current_node.is_end_of_word = true
  end

  def search(word)
    current_node = @root
    word.each_char do |char|
      return false unless current_node.children[char]

      current_node = current_node.children[char]
    end
    current_node.is_end_of_word
  end

  def starts_with(prefix)
    current_node = @root
    prefix.each_char do |char|
      return false unless current_node.children[char]

      current_node = current_node.children[char]
    end
    true
  end
end

Utilisation de l'Arbre de Préfixe

Maintenant que nous avons notre classe Trie, voyons comment l'utiliser pour insérer et rechercher des mots.

trie = Trie.new
trie.insert("chat")
trie.insert("chien")
trie.insert("chouette")

puts trie.search("chat")    # true
puts trie.search("chien")   # true
puts trie.search("cheval")  # false
puts trie.starts_with("ch")  # true
puts trie.starts_with("ca")  # false

Fonctionnalités Avancées

Nous pouvons également ajouter d'autres fonctionnalités à notre arbre de préfixe, comme la suppression de mots ou la recherche de tous les mots avec un certain préfixe. Voici comment nous pourrions implémenter la recherche de tous les mots avec un préfixe donné.

Recherche de Mots avec un Préfixe

def find_words_with_prefix(prefix)
  current_node = @root
  prefix.each_char do |char|
    return [] unless current_node.children[char]

    current_node = current_node.children[char]
  end
  collect_words(current_node, prefix)
end

def collect_words(node, prefix)
  words = []
  words << prefix if node.is_end_of_word

  node.children.each do |char, child_node|
    words.concat(collect_words(child_node, prefix + char))
  end
  words
end

Avec cette méthode, nous pouvons maintenant rechercher tous les mots qui commencent par un certain préfixe.

trie.find_words_with_prefix("ch")  # ["chat", "chien", "chouette"]

Conclusion

Les arbres de préfixe sont des structures de données puissantes et flexibles qui peuvent être utilisées dans de nombreuses applications. En Ruby, leur implémentation est relativement simple et permet d'effectuer des opérations de recherche et d'insertion de manière efficace. Que vous souhaitiez créer un système d'autocomplétion ou gérer un dictionnaire, un arbre de préfixe peut être un excellent choix.

Nous espérons que cet article vous a aidé à comprendre comment implémenter un arbre de préfixe en Ruby. N'hésitez pas à expérimenter avec le code et à ajouter vos propres fonctionnalités pour l'adapter à vos besoins !