http://qs321.pair.com?node_id=11118281

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Hi Monks

I want to divide a list of strings into substrings. Following rules should be met:

* It must be able to set together each string with a set of substrings.

* The length of each substring should be at least 3 characters.

* The length (\$len) of all substrings added together (+2 penalty for each substring) should be as small as possible.

An example: The list @list should give as result e.g. the list of substrings @expected_substrings. The length \$len gives for this example 46.

```my @list=("set abcde-efghi 12345",
"set abcde-ijkl 12345",
"clr abcde-efghi+123",
"clr abcde-ijkl 12345");

my @expected_substrings=("set","clr"," abcde-","efghi",
"ijkl"," 12345","+123");
my \$len=@expected_substrings*2;
\$len+=length(\$_) foreach @expected_substrings;
Do you have any brilliant idea how to solve this without using long loops with many trials?

Many Thanks

Replies are listed 'Best First'.
Re: Divide a list of string into substrings
by BillKSmith (Prior) on Jun 20, 2020 at 22:39 UTC
I think that I understand your requirements.

Given a set of strings.

• Split each string into a list of substrings of at least three character each
• From the set of all possible decompositions, select the one with the lowest score

Scoring a decomposition

• Form the set of all the substrings (Keep only one of each duplicated substrings)
• Sum the lengths of all the substrings in that set.
• The score is that sum plus twice the number of substrings in the set.
• I suspect that execution time of any solution would be exponential in the total number of characters.

Bill

Hi Bill

You understood the problem. Your way guarantees the best result, but as you wrote for a longer list you will get an issue with the runtime.

What I am looking for is: Some ideas to do the job, to get a good result (low score) in a reasonable runtime even for longer lists and strings. Knowing that this fast approach might not give the optimal solution (lowest score).

Re: Divide a list of string into substrings (updated)
by AnomalousMonk (Bishop) on Jun 20, 2020 at 20:15 UTC

I don't understand all the business about scoring, but at least this gets the expected fields for the given input strings. Perhaps you can use it as a point of departure to achieve your true goals.

```c:\@Work\Perl\monks>perl -wMstrict -le
"use Test::More 'no_plan';
use Test::NoWarnings;
;;
use Data::Dump qw(dd);
;;
use List::MoreUtils qw(uniq);
;;
my @list = (
'set abcde-efghi 12345',
'set abcde-ijkl 12345',
'clr abcde-efghi+123',
'clr abcde-ijkl 12345',
);
;;
my @expected_substrings = (
'set', 'clr', ' abcde-', 'efghi', 'ijkl', ' 12345', '+123',
);
;;
my \$rx_fld1 = qr{       [[:alpha:]]{2,}   }xms;
my \$rx_fld2 = qr{  \s   [[:alpha:]]{2,} - }xms;
my \$rx_fld3 = qr{       [[:alpha:]]{3,}   }xms;
my \$rx_fld4 = qr{ [\s+] [[:digit:]]{2,}   }xms;
;;
my (@flds1, @flds2, @flds3, @flds4);
for my \$str (@list) {
my \$parsed =
my (\$fld1, \$fld2, \$fld3, \$fld4) =
\$str =~ m{
\A (\$rx_fld1) (\$rx_fld2) (\$rx_fld3) (\$rx_fld4) \z
}xms;
die qq{'\$str' parse failed} unless \$parsed;
;;
push @flds1, \$fld1;
push @flds2, \$fld2;
push @flds3, \$fld3;
push @flds4, \$fld4;
}
;;
my @got_substrings = uniq @flds1, @flds2, @flds3, @flds4;
dd \@got_substrings;
;;
is_deeply \@got_substrings, \@expected_substrings,
'extracted list ok';
"
["set", "clr", " abcde-", "efghi", "ijkl", " 12345", "+123"]

ok 1 - extracted list ok
ok 2 - no warnings
1..2
Note: uniq is also in List::Util in up-to-date versions of Perl; I'm testing under version 5.8.9.

Update: It occurs to me that the uniq-ifying step should be done on each sub-set individually before the sub-sets are combined together. This could be done with a
my @got_substrings = map { uniq @\$_ } \(@flds1, @flds2, @flds3, @flds4);
statement. The output list produced is the same.

Give a man a fish:  <%-{-{-{-<

Thanks for the nice script !

The example should just illustrate the problem. The strings in the list can be completely different and your solution will only work with this specific example.

There even might exists a better solution (with a lower score (\$len)) for this example as the given one. I am looking for an idea how to come to a good and fast solution, accepting that this solution is not the best one, which can be found. (See also the answer of Bill)

I suspect there is no "good and fast" solution. This problem, to me, has the flavor of a permutation or "traveling salesman" problem, and is probably NP-hard (or one of the other NP classes).

So here's an attempt (with a cheat) that at least gets a solution in a sort of reasonable time for this problem.

```#!/usr/bin/perl

use strict; # https://perlmonks.org/?node_id=11118281
use warnings;

my @list=("set abcde-efghi 12345",
"set abcde-ijkl 12345",
"clr abcde-efghi+123",
"clr abcde-ijkl 12345");

#my @expected_substrings=("set","clr"," abcde-","efghi",
#                         "ijkl"," 12345","+123");
#my \$len=@expected_substrings*2;
#\$len+=length(\$_) foreach @expected_substrings;

\$_ = join "\n", @list;
my \$max = 3; ########################################### BIG CHEAT FOR
+ RUNTIME

sub score { 2 * @_ + length join '', @_; }
my \$best = score( @list );

try( \$_ );
print "\n";

sub try
{
(local \$_, my @sofar) = @_;
if( !/[ -~]/ )
{
my \$score = score @sofar;
if( \$score < \$best )
{
print "\n";
use Data::Dump 'dd'; dd \$score, @sofar;
\$best = \$score;
}
return;
}
score(@sofar) >= \$best and return;
for my \$n ( reverse 0 .. \$#list )
{
my %d;
/([ -~]{3,})(?:.*?\1){\$n}(?{ \$d{\$1}++ })(*FAIL)/s;
my @d = sort { length \$b <=> length \$a } sort keys %d;
@d > \$max and \$#d = \$max - 1;
for my \$string ( @d )
{
try( s/\Q\$string\E/\t/gr, @sofar, \$string );
}
}
}

Outputs:

```(46, " abcde-", " 12345", "efghi", "ijkl", "clr", "set", "+123")

where the "46" is the score and the rest are the substrings. As it finds better scores, it will print them, but so far always seems to find a best solution first.

Re: Divide a list of string into substrings
by choroba (Archbishop) on Jun 23, 2020 at 14:28 UTC
Another option is to split and join the substrings randomly, trying to improve the score at least somehow. If we deviate too much from the best score found so far, we return to the corresponding solution and continue from there.

It doesn't always found the best solution, but it usually gets pretty close to it. Also, it found another solution with the same score:

```'set', 'abcde-', 'efghi', ' ', '123', '45', 'ijkl', 'clr', '+'
Update: this is not a valid solution, as " ", "+", and "45" are too short.

And here's the code:

Update: Fixed to only report solutions with substrings of length at least 3.

map{substr\$_->,\$_->||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]

Violates the second rule, "* The length of each substring should be at least 3 characters."

True, I forgot about that! Fixed, thanks.

map{substr\$_->,\$_->||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]
Re: Divide a list of string into substrings
by LanX (Cardinal) on Jun 20, 2020 at 19:40 UTC
Your requirements for substrings are fuzzy.

You split on

• " " (mostly excluded),
• "-" (at the end)
• "+" (at the beginning).

Your best bet is the list from a regex m/(pattern)/g

Using the result as hash keys will guaranty unique entries.

Cheers Rolf
(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery

Re: Divide a list of string into substrings
by jcb (Vicar) on Jun 22, 2020 at 04:35 UTC

This was a fun exercise and here is a script that produces the expected results (in sorted order) and should be considerably faster than a full brute force search:

```#!/usr/bin/perl
# -*- CPerl -*-

use strict;
use warnings;

# Goals:
# * Find a set of shared substrings for a set of input strings such th
+at:
# ** Each substring is at least 3 characters long.
# ** Minimize total substring length, counting each substring as extra
+ 2.

use constant MIN_SUBSTRING_LEN => 3;

# sample input:
my @list=("set abcde-efghi 12345",
"set abcde-ijkl 12345",
"clr abcde-efghi+123",
"clr abcde-ijkl 12345");
# sample output:
my @expected_substrings=("set","clr"," abcde-","efghi",
"ijkl"," 12345","+123");

# cost of a solution set
sub cost (@) {
my \$cost = PER_SUBSTRING_OVERHEAD * scalar @_;
\$cost += length shift while @_;
return \$cost
}

# algorithm:
#  attempt to split common prefixes and suffixes into separate substri
+ngs;
#  terminate when this is no longer possible
my @substrings = @list;
my \$last_output = '';

# find common prefixes
# returns [ <prefix>, <tail>... ]...
sub partition (@) {
my @strings = sort @_;
my @bins = ();
my \$prefix = \$strings;

for (my \$i = 0; \$i < @strings; \$i++) {
next if \$prefix eq substr(\$strings[\$i], 0, length \$prefix);
my \$new_prefix = \$prefix;
\$new_prefix = substr \$new_prefix, 0, -1
while length \$new_prefix
and \$new_prefix ne substr(\$strings[\$i], 0, length \$new_prefix);
if (length \$new_prefix < MIN_SUBSTRING_LEN and @strings) {
push @bins, [\$prefix,
map {substr \$_, length \$prefix} splice @strings, 0, \$i];
\$i = 0; \$prefix = \$strings;
} else {
\$prefix = \$new_prefix;
}
}
push @bins, [\$prefix, map {substr \$_, length \$prefix} splice @string
+s]
if @strings;

return @bins
}

# find prefixes
my %new_substrings = ();
my @bins = partition @substrings;
\$new_substrings{\$_}++ for map {@\$_} @bins;
@substrings = sort keys %new_substrings;

# repeat for suffixes
%new_substrings = ();
@bins = partition map scalar reverse, @substrings;
\$new_substrings{\$_}++ for map {@\$_} @bins;
@substrings = grep length, sort map scalar reverse, keys %new_substr
+ings;

\$made_progress = (\$last_output ne join(':', @substrings));
\$last_output = join(':', @substrings);
}

print "results:  (cost ",cost(@substrings),")\n";
print \$_, "\n" for @substrings;

This script does not really try to produce a minimal-cost result set at all — it simply produces a solution quickly by repeatedly "peeling off" common prefixes and suffixes. The same sub partition is used for both, by simply reversing the strings to make suffixes into prefixes. It works by finding a common prefix, reducing that prefix while traversing the sorted input, and ending a group when the prefix is below the threshold length.

(thanks to LanX for the reminder to use a hash for unique keys)

The approch is good to find a fast solution. If the common substring is in the middle of each string this solution will not find it.

If the common substring is in the middle of each string this solution will not find it.

That is the major limitation to this approach. On the other hand, your sample data did not include those and this approach could be a useful preprocessing step to greatly the reduce the volume of input before applying a much-less-efficient brute force search to find those inner common substrings, if they are even a problem.

Re: Divide a list of string into substrings
by LanX (Cardinal) on Jun 23, 2020 at 10:16 UTC
Provided Re: Divide a list of string into substrings by BillKSmith is the right interpretation...

... this smells like a problem from lattice theory plus a cost function to be minimized.

Intuitively I'd try to start to take all pairs from the input and construct their decomposition.

Then you repeat this step with the resulted set of distincts substrings as new input again.

Keep repeating again till there are no new decompositions.

Though you need to mathematically proof that intermediate steps stay optimal and that the desired solution is reached.

Cheers Rolf
(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery

Re: Divide a list of string into substrings
by LanX (Cardinal) on Jun 23, 2020 at 16:50 UTC
are overlapping substrings allowed?

```"333X111",
"222X111",
"000X333",
"000X111"

With overlap "000X","X111","222","333" weight => 22

Otherwise what is the solution???

##### update

Cheers Rolf
(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery

> Otherwise what is the solution???

My program (changing the tolerance to int rand 5) says

```Score 27
\$VAR1 = [
[
'333',
'X111'
],
[
'222',
'X111'
],
[
'000',
'X333'
],
[
'000',
'X111'
]
];