*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)
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 :)
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
