Пройдя через три, чтобы получить все слова

Question

Я написал код на Perl, чтобы фактически создать структуру данных Trie , используя набор слов в массиве. Теперь у меня проблемы с прохождением и печатью слов.

Также вставил вывод Dumper созданной структуры данных.

Последний набор слов после обхода, похоже, не верен, поскольку логика обхода, безусловно, чего-то не хватает. Но создание Trie хорошо и работает быстро. Может ли кто-нибудь помочь мне здесь?

Верхний уровень дерева - хеш

1. Каждый хэш-элемент имеет ключ, который является буква и каждый хэш указывает на ссылка на массив.

2. Массив ref снова содержит список хэшей и каждый элемент хеша такой же как 1

Если вы видите первое слово в выводе. Это выглядит как archtopriumwe .

Мы должны получить дугу, арку, верх, атриум, благоговение

КОД

use Data::Dumper;
my %mainhash;

## Subroutine
sub storeword   {
    my $type = shift;
    my $fc = shift;
    my $word = shift;
    return if ((not defined $word) or (length($word) == 0));    
    my @letters =  split (//,$word);
    my $len = scalar(@letters) - 1;
    my ($arr_ref,$pass_ref,$flag ,$i,$hashitem,$newitem);
    $pass_ref = $hashitem = $new_item = undef;
    $arr_ref = $type;
    $setstop = 1 if (length($word) == 1);   
    $flag =0;
    for($i = 0;$i {$letters[0]}) {
            $flag =1;
            $pass_ref = $hashitem->{$letters[0]};
            last;
        }
    }
    if ($flag == 0) {
        $newitem->{$letters[0]} = [];   
        push(@$arr_ref,$newitem);
        $pass_ref = $newitem->{$letters[0]};
    }

    storeword($pass_ref,$letters[0],join ('',@letters[ 1..$len]));
}

## Subroutine
sub process {
    my ($prefix,$trie) = @_;
    for my $letter (sort keys %$trie) {
        if ( @{ $trie->{$letter} } ) {
            for my $branch (@{ $trie->{$letter} }) {
                process("$prefix$letter", $branch);
            }
        }
        else {
            print "$prefix$letter\n";
        }
    }
}

##main

##list of words
my @wd =  qw (arc atop awe blob boil fame tub arch atrium);

##inserting each word into the datastructure
foreach my $w (@wd) {
    my @letters = split (//,$w);
    my $len = scalar(@letters) - 1;
    if (not exists $mainhash{$letters[0]})  {
        $mainhash{$letters[0]} = [];
    }
    storeword($mainhash{$letters[0]},$letters[0],join ('',@letters[ 1..$len])); 
}
    print Dumper(%mainhash);
        ## Trying to print each word from trie.
    print("\n List of words\n");    
    process('',\%mainhash);

Выход:

$VAR1 = 'a';
$VAR2 = [
          {
            'r' => [
                     {
                       'c' => [
                                {
                                  'h' => []
                                }
                              ]
                     }
                   ]
          },
          {
            't' => [
                     {
                       'o' => [
                                {
                                  'p' => []
                                }
                              ]
                     },
                     {
                       'r' => [
                                {
                                  'i' => [
                                           {
                                             'u' => [
                                                      {
                                                        'm' => []
                                                      }
                                                    ]
                                           }
                                         ]
                                }
                              ]
                     }
                   ]
          },
          {
            'w' => [
                     {
                       'e' => []
                     }
                   ]
          }
        ];
$VAR3 = 'b';
$VAR4 = [
          {
            'l' => [
                     {
                       'o' => [
                                {
                                  'b' => []
                                }
                              ]
                     }
                   ]
          },
          {
            'o' => [
                     {
                       'i' => [
                                {
                                  'l' => []
                                }
                              ]
                     }
                   ]
          }
        ];
$VAR5 = 'f';
$VAR6 = [
          {
            'a' => [
                     {
                       'm' => [
                                {
                                  'e' => []
                                }
                              ]
                     }
                   ]
          }
        ];
$VAR7 = 't';
$VAR8 = [
          {
            'u' => [
                     {
                       'b' => []
                     }
                   ]
          }
        ];

List of words
archtopriumwe
bloboil
fame
tub

Answer 1

Видите ли вы, что ваш код как есть печатает каждую букву в структуре данных только один раз, а не один раз для каждого слова, в котором он находится?И печатать новую строку только один раз для каждой буквы верхнего уровня в дереве, а не по одной на слово?

Чтобы это исправить, вам нужно передать еще немного контекста в рекурсивную подпрограмму.Примерно так:

sub process {
    my ($prefix, $trie) = @_;
    for my $letter (sort keys %$trie) {
        if ( @{ $trie->{$letter} } ) {
            for my $branch (@{ $trie->{$letter} }) {
                process("$prefix$letter", $branch);
            }
        }
        else {
            print "$prefix$letter\n";
        }
    }
}

print("\n List of words\n");
process('', \%mainhash);

Это не печатает дугу, потому что в своей структуре данных вы не можете сказать, что дуга - это слово, но, например, boi - нет.Значение для каждой буквы должно содержать две вещи: логический индикатор того, что это конец слова, и список возможных следующих букв и их поддеревьев.