Gweithredu Coed Rhagddodiad yn Ruby

Mae coed rhagddodiad, neu "prefix trees", yn strwythurau data pwerus sy'n cael eu defnyddio'n bennaf ar gyfer storio a chwilio am eiriau. Mae'r strwythur hwn yn caniatáu i ni wneud chwiliadau cyflym ar eiriau sy'n rhannu rhannau cyffredin. Yn yr erthygl hon, byddwn yn archwilio sut i weithredu coed rhagddodiad yn Ruby, gan roi enghreifftiau cod a thipiau defnyddiol ar hyd y ffordd.

Beth yw Coed Rhagddodiad?

Mae coed rhagddodiad yn strwythurau data sy'n seiliedig ar nodau, lle mae pob nodyn yn cynrychioli un llythyren o eiriau. Mae'r coed hyn yn arbennig o ddefnyddiol ar gyfer gweithgareddau fel chwilio am eiriau, awgrymiadau, a hyd yn oed geiriau sy'n dechrau gyda phennod benodol. Mae'r strwythur yn caniatáu i ni storio eiriau yn effeithlon, gan leihau'r gofod a'r amser chwilio.

Strwythur Coed Rhagddodiad

Mae coed rhagddodiad yn cynnwys nodau sy'n gysylltiedig â'i gilydd. Mae pob nodyn yn cynnwys:

Y llythyren sy'n gysylltiedig â'r nodyn.
Map o blant sy'n gysylltiedig â'r nodyn hwnnw.
Flag sy'n nodi a yw'r nodyn yn ddiweddglo ar gyfer gair.

Dyma enghraifft o strwythur nodyn yn Ruby:

class Node
  attr_accessor :children, :is_end_of_word

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

Creu Coed Rhagddodiad

Y cam cyntaf i greu coed rhagddodiad yw creu'r dosbarth sy'n cynrychioli'r goeden. Byddwn yn defnyddio'r dosbarth Node a chreu dosbarth Tree sy'n defnyddio'r nodau hyn.

class PrefixTree
  def initialize
    @root = Node.new
  end
end

Mae'r dosbarth PrefixTree yn cynnwys nodyn gwreiddiol, sy'n nodi'r dechrau o'r goeden. Nawr, gadewch i ni ychwanegu dull i ychwanegu eiriau i'r goeden.

Ychwanegu Eiriau

Mae'r dull i ychwanegu gair yn dechrau o'r nodyn gwreiddiol ac yn mynd i lawr y goeden, gan greu nodau newydd pan fo angen. Dyma'r dull:

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

Mae'r dull hwn yn mynd trwy bob llythyren yn y gair, gan greu nodau newydd os nad ydynt eisoes yn bodoli. Pan fydd y gair wedi'i ychwanegu, mae'r flag is_end_of_word yn cael ei osod i wir.

Chwilio am Eiriau

Un o'r prif fanteision o ddefnyddio coed rhagddodiad yw'r gallu i chwilio am eiriau. Gadewch i ni ychwanegu dull i chwilio am eiriau yn y goeden.

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

Mae'r dull search yn gweithio yn debyg i'r dull insert, ond yn gwirio a yw pob llythyren yn bodoli yn y goeden. Os yw'r gair yn bodoli, bydd yn dychwelyd gwir; os na, bydd yn dychwelyd ffug.

Chwilio am Eiriau gyda Rhagddodiad

Gallwn hefyd ychwanegu dull i chwilio am eiriau sy'n dechrau gyda rhannau penodol. Mae hyn yn ddefnyddiol ar gyfer awgrymiadau eiriau. Dyma'r dull:

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

Mae'r dull starts_with yn gwirio a yw'r rhannau penodol yn bodoli yn y goeden, gan ddychwelyd gwir os ydynt yn bodoli.

Enwogion a Defnyddiau

Mae coed rhagddodiad yn cael eu defnyddio mewn llawer o gymwysiadau, gan gynnwys:

Chwilio am eiriau yn y geiriadur.
Awgrymiadau eiriau yn ystod teipio.
Gweithredu systemau rheoli geiriau.
Chwilio am eiriau yn y ffeiliau testun.

Mae'r strwythur hwn yn arbennig o ddefnyddiol pan fo angen chwilio am eiriau yn gyflym, gan ei fod yn lleihau'r amser a'r gofod sydd ei angen ar gyfer storio eiriau.

Casgliad

Mae coed rhagddodiad yn strwythurau data pwerus sy'n cynnig llawer o fanteision ar gyfer storio a chwilio am eiriau. Trwy ddefnyddio Ruby, gallwn greu coed rhagddodiad sy'n gallu ychwanegu, chwilio, a gwirio rhannau penodol o eiriau. Mae'r dulliau a drafodwyd yn yr erthygl hon yn cynnig sylfaen gadarn ar gyfer datblygu cymwysiadau sy'n seiliedig ar eiriau.

Gobeithio bod yr erthygl hon wedi bod yn ddefnyddiol ac yn gyfeillgar wrth i chi archwilio'r byd o goed rhagddodiad yn Ruby. Peidiwch ag oedi i gysylltu os oes gennych unrhyw gwestiynau neu os hoffech drafod mwy am y pwnc hwn!