Re: Counting the number of repeated phrases in a column

Le 27/01/2022 à 18:35, Merlin Moncure a écrit :
> On Thu, Jan 27, 2022 at 11:09 AM Rob Sargent <robjsargent@gmail.com> wrote:
>>
>> On 1/27/22 10:03, Merlin Moncure wrote:
>>
>> On Wed, Jan 26, 2022 at 5:23 PM Merlin Moncure <mmoncure@gmail.com> wrote:
>>
>> with s as (select 'Hello World Hello World' as sentence)
>> select
>>    phrase,
>>    array_upper(string_to_array((select sentence from s), phrase), 1) -
>> 1 as occurrances
>> from
>> (
>>    select array_to_string(x, ' ') as phrase
>>    from
>>    (
>>      select distinct v[a:b]  x
>>      from regexp_split_to_array((select sentence from s), ' ') v
>>      cross join lateral generate_series(1, array_upper(v, 1)) a
>>      cross join lateral generate_series(a + 1, array_upper(v, 1)) b
>>    ) q
>> ) q;
>>
>> Simplified to:
>> select distinct array_to_string(v[a:b], ' ') phrase, count(*) as occurrences
>> from regexp_split_to_array('Hello World Hello World', ' ') v
>> cross join lateral generate_series(1, array_upper(v, 1)) a
>> cross join lateral generate_series(a + 1, array_upper(v, 1)) b
>> group by 1;
>>
>>           phrase          │ occurances
>> ─────────────────────────┼────────────
>>   World Hello             │          1
>>   Hello World Hello       │          1
>>   Hello World             │          2
>>   Hello World Hello World │          1
>>   World Hello World       │          1
>>
>> merlin
>>
>>
>> And since we're looking for repeated phrases maybe add
>>
>> having count(*) > 1
>
> thanks.  also, testing on actual data, I noticed that a couple other
> things are mandatory, mainly doing a bit of massaging before
> tokenizing:
>
> select distinct array_to_string(v[a:b], ' ') phrase, count(*) as occurrences
> from
> (
>    select array_agg(t) v
>    from
>    (
>      select trim(replace(unnest(v), E'\n', '')) t
>      from regexp_split_to_array(<sentence>, ' ') v
>    ) q
>    where length(t) > 1
> ) q
> cross join lateral generate_series(1, array_upper(v, 1)) a
> cross join lateral generate_series(a + 1, array_upper(v, 1)) b
> group by 1
> having count(*) > 1;
>
> We are definitely in N^2 space here, so look for things to start
> breaking down for sentences > 1000 words.
>
> merlin
>

(for better complexity) you may search about "Ukkonen suffix tree"
Similar problem as yours :
https://www.geeksforgeeks.org/suffix-tree-application-3-longest-repeated-substring/?ref=lbp