字符串分割问题

TrishaTie

给定一个字符串， 和一个单词列表。 有没有大神帮忙给个思路。

Now, please decompose OOV words into the mixture of W* and S*, which means this word can be constructed with multiple words and segments. Every word still has length >=3.
1)        This means for the OOV, first search the 27k valid word list, and find the maximum match word W1.
2)        Then for the remaining segments (e.g., S1 W1 S2), search the word list again to find the maximum word W2 (e.g., S1 W1 S3 W2 S4).
3)        Repeat the process until you cannot  find any matching word with length >=3.   

测试：
$string='WHAT'SATDSYOURATIP';

WordLIST：
WHAT'S
YOUR
TIP

Output:
WHAT'S
ATDS
YOUR
A
TIP

rubyish

回复 1# TrishaTie

给个思路。

1, 2, 3 jiushi silu ~~

1)        This means for the OOV, first search the 27k valid word list, and find the maximum match word W1.
2)        Then for the remaining segments (e.g., S1 W1 S2), search the word list again to find the maximum word W2 (e.g., S1 W1 S3 W2 S4).
3)        Repeat the process until you cannot  find any matching word with length >=3.   

123 de silu:

output:

1. OOV:
   
2. WHAT'SATDSYOURATIP
   
3. 
   
4. decompose:
   
5. WHAT'S ATDS YOUR A TIP
   
6. ----------------------------------------------------------------
   
7. OOV:
   
8. Repeattheprocessuntilyoucannotfindanymatchingwordwithlength
   
9. 
   
10. decompose:
    
11. Repeat the process until you cannot find any matching word with length
    
12. ----------------------------------------------------------------
    
13. OOV:
    
14. NowpleasedecomposeOOVwordsintothemixtureofandwhichmeansthiswordcanbeconstructedwithmultiplewords
    
15. 
    
16. decompose:
    
17. Now please decompose OOV words into the mixture of and which means this word can be constructed with multiple words
    
18. ----------------------------------------------------------------
    
19. 
    

复制代码

biru.pl

1. #!/usr/bin/perl
   
2. 
   
3. use 5.010;
   
4. 
   
5. # the 27k valid word list
   
6. my @the27k =
   
7.   qw[Every Repeat Then This again and any can cannot constructed decompose find first for has into length list match matching maximum means mixture multiple please process remaining search segments still TIP the this until valid WHAT'S which with word words you YOUR
   
8. ];
   
9. 
   
10. my $length = 3;
    
11. 
    
12. # the maximum match word
    
13. @the27k = sort { length($b) <=> length($a) } @the27k;
    
14. 
    
15. while (<DATA>) {
    
16.     chomp;
    
17.     say "OOV:\n$_\n";
    
18.     my @words = decompose($_);
    
19.     say 'decompose:';
    
20.     say "@words";
    
21.     say '-' x 64;
    
22. }
    
23. 
    
24. # ____________________SUB____________________
    
25. 
    
26. sub decompose {
    
27.     my $segment = shift;
    
28. 
    
29.     # length < 3
    
30.     if ( length($segment) < $length ) {
    
31.         return $segment;
    
32.     }
    
33.     my ( $index, $find ) = ( -1, '' );
    
34. 
    
35.     # search the 27k valid word list
    
36.     for my $word (@the27k) {
    
37.         $index = index( $segment, $word );
    
38.         next if $index < 0;
    
39.         $find = $word;
    
40.         last;
    
41.     }
    
42. 
    
43.     # you cannot find any matching word with length >=3
    
44.     return $segment if $index < 0;
    
45. 
    
46.     # Then for the remaining segments, search the word list again
    
47.     my $S1 = substr $segment, 0, $index;
    
48.     my $S2 = substr $segment, $index + length($find);
    
49. 
    
50.     # Repeat the process
    
51.     $S1 ? decompose($S1) : (),
    
52.     $find,
    
53.     $S2 ? decompose($S2) : ();
    
54. 
    
55. }
    
56. __DATA__
    
57. WHAT'SATDSYOURATIP
    
58. Repeattheprocessuntilyoucannotfindanymatchingwordwithlength
    
59. NowpleasedecomposeOOVwordsintothemixtureofandwhichmeansthiswordcanbeconstructedwithmultiplewords

复制代码

TrishaTie

@rubyish， 非常感谢！

本地跑了一下，确实是我想实现的东西。

不过 最后一个部分  没有很看懂。
&nbsp; &nbsp; # Repeat the process
&nbsp; &nbsp; $S1 ? decompose($S1) : (),
&nbsp; &nbsp; $find,
&nbsp; &nbsp; $S2 ? decompose($S2) : ();

我可以理解为： 《》中间的 和 decompose($S1) 去做选择？ 求解释。

$S1 ? decompose($S1) : 《 (), $find, $S2 ? decompose($S2) : ()》；

rubyish

回复 3# TrishaTie

我可以理解为： 《》中间的 和 decompose($S1) 去做选择？

no ~~

biru:
3 * 5 + 6 + 4 * 5 = ( 3 * 5 ) + 6 + ( 4 * 5 )
!= 3 * ( 5 + 6 + 4 ) * 5

precedence [?:] > [,]

1. $S1 ? decompose($S1) : (),
   
2. $find,
   
3. $S2 ? decompose($S2) : ();

复制代码

EQ

1. ($S1 ? decompose($S1) : ()),
   
2. $find,
   
3. ($S2 ? decompose($S2) : ());

复制代码

EQ

1. my @S1 = $S1 ? decompose($S1) : ();
   
2. my @S2 = $S2 ? decompose($S2) : ();
   
3. return @S1, $find, @S2;

复制代码

TrishaTie

rubyish 发表于 2017-11-03 00:43
回复 3# TrishaTie

no ~~

谢谢 rubyish  大神 大半夜回复 消息， 哦    那我就是$find 那个地方 混了， 然后曲解了整句话的含义。
再次感谢  
想说 早点睡  哈哈

523066680

回复 5# TrishaTie

有时差

TrishaTie

其实我想说的是， 当我 wordlist 有2w多个的时候，而且，需要查找的单词很多的时候， 这样是不是很费时间， 因为用C# 实现了一遍，实现一部分数据，需要超级多的时间。 我如果 存 wordlist 到hash, 去遍历每个单词字符的时候，会不会省时间。

rubyish

shishi hash ~~

1. #!/usr/bin/perl
   
2. # version 26, subversion 1 (v5.26.1)
   
3. use 5.010;
   
4. 
   
5. my @list = qw[
   
6.   Book Both Camel Cite Every Extraction Language Larry Originally Page Perl Permanent Practical Programming Related Repeat Reporting Since Special TIP Then This Though Unix Upload VALID WHAT'S Wall What Wikidata YOUR acronym again and another any are backronyms became because began book borrow bumped but can cannot change changes constructed continue cover decompose compose developed development different documentation documented easier eventually evolved facto file find first for from general has here ideas identify including independently information into item its known language languages length lengthy liberally link links list major make man many mark match matching maximum means mixture multiple not number officially one only originally page pages please process processing programmers published purpose redesign reference remaining report revisions robot same scripting search segments separate single still teams that the then there this time undergone until use various version was well which with word words you your sword
   
7. ];
   
8. 
   
9. my $lexicon = from( \@list );
   
10. 
    
11. while (<DATA>) {
    
12.     say "OOV:\n$_";
    
13.     say 'decompose:';
    
14.     chomp;
    
15.     decompose($_);
    
16.     say '-' x 64;
    
17. }
    
18. 
    
19. # ____________________SUB____________________
    
20. 
    
21. sub from {
    
22.     my $words   = shift;
    
23.     my $lexicon = {};
    
24. 
    
25.     for my $word (@$words) {
    
26.         my @chara = split '', $word;
    
27.         my $dit   = $lexicon;
    
28. 
    
29.         for my $k (@chara) {
    
30.             $dit = $dit->{$k} //= {};
    
31.         }
    
32. 
    
33.         $dit->{'@'} = 1;
    
34.     }
    
35. 
    
36.     return $lexicon;
    
37. }
    
38. 
    
39. sub decompose {
    
40.     my $unknown = shift;
    
41.     my @unknown = split '', $unknown;
    
42.     my $fate    = $#unknown;
    
43.     my @sigil   = (0) x @unknown;
    
44. 
    
45.     for my $i ( 0 .. $fate ) {
    
46.         my $dit = $lexicon;
    
47. 
    
48.         for my $j ( $i .. $fate ) {
    
49.             $dit = $dit->{ $unknown[$j] };
    
50.             last unless $dit;
    
51. 
    
52.             if ( $dit->{'@'} ) {
    
53.                 $sigil[$i] = $j - $i + 1;
    
54.             }
    
55.         }
    
56.     }
    
57. 
    
58.     say join ' ', D_( $unknown, \@sigil, 0, [ 0, $#sigil ] );
    
59. }
    
60. 
    
61. sub D_ {
    
62.     my ( $unknown, $sigil, $need, $range ) = @_;
    
63.     my ( $r1, $r2 ) = @$range;
    
64.     my ( $fine, $indes ) = ( 0, 0 );
    
65. 
    
66.     modify( $unknown, $sigil, $r1, $r2 ) if $need;
    
67. 
    
68.     for my $i ( $r1 .. $r2 ) {
    
69.         next if $sigil->[$i] <= $fine;
    
70. 
    
71.         $fine  = $sigil->[$i];
    
72.         $indes = $i;
    
73.     }
    
74. 
    
75.     if ( !$fine ) {
    
76.         return substr $unknown, $r1, $r2 - $r1 + 1;
    
77.     }
    
78. 
    
79.     my $find = substr $unknown, $indes, $fine;
    
80.    
    
81.     $r1 <= $indes - 1
    
82.       ? D_( $unknown, $sigil, 1, [ $r1, $indes - 1 ] )
    
83.       : (),
    
84.     $find,
    
85.     $indes + $fine <= $r2
    
86.       ? D_( $unknown, $sigil, 0, [ $indes + $fine, $r2 ] )
    
87.       : ();
    
88. }
    
89. 
    
90. sub modify {
    
91.     my ( $unknown, $sigil, $r1, $r2 ) = @_;
    
92. 
    
93.     for my $i ( $r1 .. $r2 ) {
    
94.         next unless $sigil->[$i];
    
95.         next if $i + $sigil->[$i] - 1 <= $r2;
    
96. 
    
97.         my $dit = $lexicon;
    
98.         $sigil->[$i] = 0;
    
99. 
    
100.         for my $j ( $i .. $r2 ) {
     
101.             $dit = $dit->{ substr( $unknown, $j, 1 ) };
     
102. 
     
103.             if ( $dit->{'@'} ) {
     
104.                 $sigil->[$i] = $j - $i + 1;
     
105.             }
     
106.         }
     
107.     }
     
108. }
     
109. 
     
110. __DATA__
     
111. WHAT'SATDSYOURATIP
     
112. themixtureofandwhichmeansthiswordcan
     
113. ThoughPerlisnotofficiallyanacronymtherearevariousbackronymsinuseincludingPracticalExtractionandReportingLanguagePerlwasoriginallydevelopedbyLarryWallin1987asageneralpurposeUnixscriptinglanguagetomakereportprocessingeasierSincethenithasundergonemanychangesandrevisionsPerl6whichbeganasaredesignofPerl5in2000eventuallyevolvedintoaseparatelanguageBothlanguagescontinuetobedevelopedindependentlybydifferentdevelopmentteamsandliberallyborrowideasfromoneanother
     

复制代码