How to get the longest "overlapping" words

user_474287 0
Viewed 181

Premise: Suppose you have a table containing words, where some may be distinct and some "may overlap", meaning a longer word starts with a shorter one, eg:

---------------
|    word     |
---------------
| dog         | *
| games       | *
| stat        |
| state       | 
| statement   | *
| fulfill     |
| fulfilled   | *
| fulfillment | *
---------------

Question: How does one write a query that returns the list of non-overlapping + the longest overlapping words in such cases?

In the example above, the desired words are identified by a *, as per the following extended explanation:

  • dog and games don't overlap with anything, so they're the longest in their "solo/distinct" category
  • statement overlaps with state and stat and is the longest
  • fulfilled overlaps with fulfill and is longer (does NOT overlap with fulfillment)
  • fulfillment overlaps with fulfill and is longer (does NOT overlap with fulfilled)

Note: Please be aware that for the sake of simplicity, the data sample is reduced. In reality there are a few million records to query and, there are no search terms known before hand, so it's not possible to directly use constructs such as WHERE word LIKE 'stat%'. Not sure if relevant or not, but the words have a relatively short max length, eg 20.

oracle sql
4 Answers

Something like

select word
from   your_table t1
where  not exists (
                    select word
                    from   your_table t2
                    where  t2.word like t1.word || '_%'
                  )
;

The query would benefit from the existence of an index on word. But even then it may take a long time. In any case, you can give it a try and let us know what happens.

Admin1

As long as you compare prefixes and if one word is entirely included as prefix of the other, you may try match_recognize to sequentially check prefix-matching in one pass.

But exists is more clear, though you should examine performace on your real dataset with index on word.

with a as (
  select
    column_value as word
  from sys.odcivarchar2list(
    'dog'
    , 'games'
    , 'stat'
    , 'state'
    , 'statement'
    , 'fulfill'
    , 'fulfilled'
    , 'fulfillment'
  )
)
select *
from a 
match_recognize(
  order by word desc /*Longest first*/
  measures
    a.word as word
  one row per match
  /*Exclude any number of words
    each of which is a prefix of the previous one
  */
  pattern (a {- b* -})
  define
    /*Current word is a prefix of the previous*/
    b as prev(word) like word || '%'
) t

| WORD        |
| :---------- |
| statement   |
| games       |
| fulfillment |
| fulfilled   |
| dog         |

db<>fiddle here

user_27787100

How does one write a query that returns the list of non-overlapping + the longest overlapping words in such cases?

You can do it in a single table scan with a hierarchical query:

SELECT word,
       MAX(PRIOR word) AS substring
FROM   words
WHERE  CONNECT_BY_ISLEAF = 1
AND    LEVEL IN (1,2)
CONNECT BY word LIKE PRIOR word || '%'
AND        PRIOR ROWID != ROWID
GROUP BY word;

Which, for the sample data:

CREATE TABLE words (word) AS
SELECT 'dog' FROM DUAL UNION ALL
SELECT 'games' FROM DUAL UNION ALL
SELECT 'stat' FROM DUAL UNION ALL
SELECT 'state' FROM DUAL UNION ALL
SELECT 'statement' FROM DUAL UNION ALL
SELECT 'fulfill' FROM DUAL UNION ALL
SELECT 'fulfilled' FROM DUAL UNION ALL
SELECT 'fulfillment' FROM DUAL;

Outputs:

WORD SUBSTRING
dog
games
statement state
fulfilled fulfill
fulfillment fulfill

db<>fiddle here

Update

You can also get the longest sub-string match using MATCH_RECOGNIZE:

SELECT word,
       substring
FROM   words
MATCH_RECOGNIZE (
  ORDER BY word DESC
  MEASURES
    PREV(word.word) AS prev_word,
    word.word AS word,
    substring.word AS substring
  ONE ROW PER MATCH
  AFTER MATCH SKIP TO NEXT ROW
  PATTERN (word (non_substring*? substring)?)
  DEFINE
    substring     AS word.word LIKE word || '_%'
)
WHERE  prev_word IS NULL
OR     prev_word NOT LIKE word || '%'

Which, for the sample data, gives the same output as above.

db<>fiddle here

user_15092640

You may simple sort the words and discard all words that are the prefix of the following word.

You must consider the last word (see the OR predicate in the where condition)

with words as (
select WORD,
lead(WORD) over (order by WORD) WORD_LEAD
from tabs )
select word 
from words
where word != substr( WORD_LEAD, 1, length(word)) or WORD_LEAD is NULL /* last word */
order by word;

result

WORD 
-----------
dog
fulfilled
fulfillment
games
statement

This solution covers the duplicates as well and does not contains the prohibitive FILTER operation as other proposals that would trottle the performance for large tables (except for the match_recognizesolution).

user_48081220
Related