Count unique appearance of substring in a list of

Question

*I try to count the unique appearances of a substring inside a list of words * So check the list of words and detect if in any words there are substrings based on min characters that occur multiple times and count them. I don't know any substrings.

This is a working solution where you know the substring but what if you do not know ? Theres a Minimum Character count where words are based on.

Will find all the words where "Book" is a substring of the word. With below php function.

Wanted outcome instad:

book count (5)
stor count (2)

Answer 1

Given a string of length 100

book bookstore bookworm booking book cooking boring bookingservice.... ok
0123456789...                                                     ... 100

your algorithm could be:

Investigate substrings from different starting points and substring lengths. You take all substrings starting from 0 with a length from 1-100, so: 0-1, 0-2, 0-3,... and see if any of those substrings accurs more than once in the overall string. Progress through the string by starting at increasing positions, searching all substrings starting from 1, i.e. 1-2, 1-3, 1-4,... and so on until you reach 99-100.

Keep a table of all substrings and their number of occurances and you can sort them.

You can optimize by specifying a minimum and maximum length, which reduces your number of searches and hit accuracy quite dramatically. Additionally, once you find a substring save them in a array of searched substrings. If you encounter the substring again, skip it. (i.e. hits for book that you already counted you should not count again when you hit the next booksubstring). Furthermore you will never have to search strings that are longer than half of the total string.

For the example string you might run additional test for the uniquness of a string. You'd have

o              x ..
oo             x  7
bo             x  7
ok             x  6 
book           x  5
booking        x  2
bookingservice x  1

with disregarding stings shorter than 3 (and longer than half of total textstring), you'd get

book           x  5
booking        x  2
bookingservice x  1

which is already quite a plausible result.

[edit] This would obviously look through all of the string, not just natural words.

[edit] Normally I don't like writing code for OPs, but in this case I got a bit interested myself:

$string = "book bookshelf booking foobar bar booking ";
$string .= "selfservice bookingservice cooking";

function search($string, $min = 4, $max = 16, $threshhold = 2) {
    echo "<pre><br/>";
    echo "searching <em>'$string'</em> for string occurances ";
    echo "of length $min - $max: <br/>";

    $hits = array();
    $foundStrings = array();

    // no string longer than half of the total string will be found twice
    if ($max > strlen($string) / 2) {
        $max = strlen($string);
    }

    // examin substrings:
    // start from 0, 1, 2...
    for ($start = 0; $start < $max; $start++) {

        // and string length 1, 2, 3, ... $max
        for ($length = $min; $length < strlen($string); $length++) {

            // get the substring in question, 
            // but search for natural words (trim)
            $substring = trim(substr($string, $start, $length));

            // if substring was not counted yet, 
            // add the found count to the hits
            if (!in_array($substring, $foundStrings)) {
                preg_match_all("/$substring/i", $string, $matches);
                $hits[$substring] = count($matches[0]);
            }
        }
    }

    // sort the hits array desc by number of hits
    arsort($hits);

    // remove substring hits with hits less that threshhold
    foreach ($hits as $substring => $count) {
        if ($count < $threshhold) {
            unset($hits[$substring]);
        }
    }

    print_r($hits);
}

search($string);

?>

The comments and variable names should make the code explain itself. $string would come for a read file in your case. This exmaple would output:

searching 'book bookshelf booking foobar bar booking selfservice 
bookingservice cooking' for string occurances of length 4 - 16: 
Array
(
    [ook] => 6
    [book] => 5
    [boo] => 5
    [bookin] => 3
    [booking] => 3
    [booki] => 3
    [elf] => 2
)

Let me know how you implement it :)

Answer 2

This is my first approximation: unfinished, untested, has at least 1 bug, and is written in eiffel. Well I am not going to do all the work for you.

deferred class
    SUBSTRING_COUNT
feature
    threshold : INTEGER_32 =5

    biggest_starting_substring_length(a,b:STRING):INTEGER_32
        deferred
    end

    biggest_starting_substring(a,b:STRING):STRING
    do
        Result := a.substring(0,biggest_starting_substring_length(a,b))
    end

    make_list_of_substrings(a,b:STRING)
    local
        index:INTEGER_32
        this_one: STRING
    do
        from
            a_index := b_index + 1
        invariant
            a_index >=0 and a_index <= a.count
        until
            a_index >= a.count
        loop
            this_one := biggest_starting_substring(a.substring (a_index, a.count-1),b)
            if this_one.count > threshold then
                list.extend (this_one)
            end
        variant
            a.count - a_index
        end
    end -- biggest_substring

    list : ARRAYED_LIST[STRING]

end