From: Xavier Noria <fxn@...>
Date: 2007-08-07T20:09:35+09:00
Subject: Re: Determining the common prefix for several strings

On Aug 7, 2007, at 3:47 AM, Logan Capaldo wrote:

> On 8/6/07, Xavier Noria <fxn@hashref.com> wrote:
>>
>> El Aug 6, 2007, a las 5:13 PM, Stefan Rusterholz escribi�:
>>
>>> Wow, I'm surprised nobody had the idea of simply using Array#abbrev,
>>> which is included in the stdlib.
>>
>> There's no guarantee you can obtain the maximum common prefix from
>> its output, because it computes _unambiguous_ prefixes:
>>
>>    %w{ item1 item2 }.abbrev
>>    => {"item1"=>"item1", "item2"=>"item2"}
>>
>> See, no "item" there, you end up basically with the information you
>> had before the call.
>
>
>
> irb(main):027:0>    items = [
> irb(main):028:1*     'item001',
> irb(main):029:1*     'item004',
> irb(main):030:1*     'item002',
> irb(main):031:1*     'item002b',
> irb(main):032:1*     'item002C',
> irb(main):033:1*     'item 5',
> irb(main):034:1*     'item 10',
> irb(main):035:1*     'itemize this'
> irb(main):036:1>   ]
> irb(main):039:0> Abbrev.abbrev(items).sort_by { |s,|  
> s.length}.first.first[0..-
> 2]
> => "item"
> irb(main):040:0> items = ["happy", "happening", "hapless"]
> => ["happy", "happening", "hapless"]
> irb(main):041:0> Abbrev.abbrev(items).sort_by { |s,|  
> s.length}.first.first[0..-
> 2]
> => "hap"
> irb(main):042:0> items = ["c", "b", "a"]
> => ["c", "b", "a"]
> irb(main):043:0> Abbrev.abbrev(items).sort_by { |s,|  
> s.length}.first.first[0..-
> 2]
> => ""
> irb(main):044:0>
>
> I've edited out some false starts. Please feel free to point out  
> any flaws
> that I've missed

If I understand correctly that approach that says: "since I can get  
some absolute shortest (perhaps not unique as fas as length is  
concerned) unambiguous minimum, belonging to string S, that shortest  
minus one is ambiguous". That's the key idea, and I think there's  
something into it.

What happens is that, as far as I can see, you can only conclude  
there's ambiguity with some other string, which is not the same than  
saying that you've got the maximum common prefix. See for example:

   %w{abc acb abd acd}.abbrev.sort_by {|s,| s.length}.first.first[0..-2]
   => "ac"

-- fxn 

PS: I think abbrev does too much work compared to more specific  
solutions, but it is worth exploring for the sake of thinking  
nonetheless.