Массив суффиксов и поиск подстроки в строке

Я нашел реализацию массива суффиксов в Ruby и немного изменил ее. Вот что у меня есть:

class SuffixArray
    def initialize(str)
        @string = str
        @suffix_array = []
        (0...str.length).each do |i|
            substring = @string[i...str.length]
            @suffix_array << {:suffix=>substring, :index => i}
        end

        @sorted_suffix_array = @suffix_array.sort {|x,y| x[:suffix] <=> y[:suffix]}
    end

    def print_sorted
      @sorted_suffix_array.each {|item| puts "#{item[:index]}=>#{item[:suffix]}"}
      puts "total=>#{@sorted_suffix_array.size()}"
    end

    def print_unsorted
      @suffix_array.each {|item| puts "#{item[:index]}=>#{item[:suffix]}"}
      puts "total=>#{@suffix_array.size()}"
    end

    def find_substring(substring)
        low = 0
        high = @sorted_suffix_array.length
        while(low <= high) do
            mid = (low + high) / 2
            comparison = @sorted_suffix_array[mid][:suffix]#[0..substring.length]
      if comparison > substring
        high = mid - 1
      elsif comparison < substring
        low = mid + 1
      else 
        return @sorted_suffix_array[mid][:index]
      end
        end
    end

end

Он работает хорошо, но не находит все подстроки, которые мне нужны. Например

a = SuffixArray.new("there is a man who likes dogs")
puts a.find_substring("man") #won't be found
puts a.find_substring("who likes dogs") #will be found
puts a.find_substring("o likes dogs") #will be found

Как изменить алгоритм, чтобы он находил все нужные мне подстроки?


ruby string full-text-search algorithm suffix-array
person Alan Coromano    schedule 20.11.2012    source источник
comment
Я знаю. Вот почему я задал вопрос.   -  person Alan Coromano    schedule 20.11.2012
comment
Вы можете поддерживать LCP массива суффиксов. (Самый длинный общий префикс) - Если вы ищете префиксы суффиксов строк в массиве суффиксов, вы должны найти подстроки! -   -  person Arvind    schedule 20.11.2012
comment
Вам больше не следует называть это суффиксом, если вы ищете произвольные подстроки, а не просто суффиксы.   -  person Mark Reed    schedule 20.11.2012

Ответы (2)


arrow_upward
1
arrow_downward

Ваш код был почти правильным. Сделал небольшие изменения и все работает.

def find_substring(substring)
  low = 0
  high = @sorted_suffix_array.length-1
  while(low <= high) do
    mid = (low + high) / 2
    comparison = @sorted_suffix_array[mid][:suffix][0...substring.length]
    if comparison > substring
      high = mid - 1
    elsif comparison < substring
      low = mid + 1
    else 
      return @sorted_suffix_array[mid][:index]
    end
  end
end
person wye.bee    schedule 20.11.2012
comment
У меня действительно это уже было. Почему вы используете @sorted_suffix_array.length-1 вместо @sorted_suffix_array.length? - person Alan Coromano; 20.11.2012
comment
При выполнении бинарного поиска low и high должны быть действительными индексами. Проверьте код на странице википедии по алгоритму бинарного поиска. - person wye.bee; 26.11.2012

arrow_upward
1
arrow_downward

Для других; ссылка, вот один без подстроки в хеше

Суть: https://gist.github.com/bluetwin/5268722

class SuffixArray

  attr_reader :suf, :string

  def initialize(string)
    @string = string
    @suf = (0..string.size-1).sort_by{|i|@string[i..-1]}
  end

  def substring(idx)
    @string[@suf[idx][email protected]]
  end

  def bsearch(str)
    low = 0
    high = @suf.length-1
    found = nil
    while(low <= high) do
      mid = (low + high) / 2
      comp = substring(mid)
      if comp > str
        high = mid - 1
      elsif comp < str
        low = mid + 1
      else
       found = comp
       low = high + 1
      end
    end
    found
  end

end
person bluetwin    schedule 29.03.2013