-1

最短共通超文字列問題の目標は、特定のセット内のすべての文字列を部分文字列として含む、可能な限り短い文字列を見つけることです。問題が「NP完全」であることは理解しています。しかし、この問題には近似戦略があります。たとえば、短い文字列が与えられた場合

ABRAC
ACADA
ADABR
DABRA
RACAD

上記の特定の文字列の出力がABRACADABRA. もう一つの例

Given

fegiach
bfgiak
hfdegi
iakhfd
fgiakhg

文字列 bfgiakhfdegiachは長さ 15 の可能な解です。

アルゴリズムの詳細な研究はありませんが、これを改善するために取り組んでいますが、Ruby でこれを実装したいと考えています。

単純な貪欲な実装には、各部分文字列の接尾辞配列の作成が含まれます

def suffix_tree(string)
  size = string.length
  suffixes = Array.new(size)
  size.times do |i|
    suffixes[i] = string.slice(i, size)
  end
  suffixes
end

#store the suffixes in a hash
#key is a fragment, value = suffixes
def hash_of_suffixes(fragments)
  suffixes_hash = Hash.new
  fragments.each do |frag|
    suffixes_hash["#{frag}"]= suffix_tree(frag)
  end
  suffixes_hash
end


fragments = ['ABRAC','ACADA','ADABR','DABRA','RACAD']
h = hash_of_suffixes(fragments)

#then search each fragment in all the suffix trees and return the number of 
#overlaps for each key

#store the results in graph??
#find possible ordering of the fragments

I would be grateful with some help.
4

1 に答える 1

1

あなたの例の問題を指摘するコメントに注意してください。また、これを行うための巧妙な方法がある場合、それが何であるかはわかりません。私はすべての順列を繰り返し、それらを一緒に滑らかにして、最短のものを見つけます。

class ShortestSuperstring
  def initialize(*strings)
    self.strings = strings
  end

  def call
    @result ||= smoosh_many strings.permutation.min_by { |permutation| smoosh_many(permutation.dup).size }
  end

  private

  attr_accessor :strings

  def smoosh_many(permutation, current_word='')
    return current_word if permutation.empty?
    next_word = permutation.shift
    smoosh_many permutation, smoosh_two(current_word, next_word)
  end

  def smoosh_two(base, addition)
    return base if base.include? addition
    max_offset(base, addition).downto 0 do |offset|
      return base << addition[offset..-1] if addition.start_with? base[-offset, offset]
    end
  end

  def max_offset(string1, string2)
    min string1.size, string2.size
  end

  def min(n1, n2)
    n1 < n2 ? n1 : n2
  end
end

そしてテストスイート：

describe ShortestSuperstring do
  def self.ss(*strings, possible_results)
    example "#{strings.inspect} can come from superstrings #{possible_results.inspect}" do
      result = described_class.new(*strings).call
      strings.each { |string| result.should include string }
      possible_results.should include(result), "#{result.inspect} was not an expected superstring."
    end
  end

  ss '', ['']
  ss "a", "a", "a", ['a']
  ss "a", "b", %w[ab ba]
  ss 'ab', 'bc', ['abc']
  ss 'bc', 'ab', ['abc']
  ss 'abcd', 'ab', ['abcd']
  ss 'abcd', 'bc', ['abcd']
  ss 'abcd', 'cd', ['abcd']
  ss 'abcd', 'a', 'b', 'c', 'd', ['abcd']
  ss 'abcd', 'a', 'b', 'c', 'd', 'ab', 'cd', 'bcd', ['abcd']

  %w[ABRAC ACADA ADABR DABRA RACAD].permutation.each do |permutation|
    ss *permutation, %w[RACADABRAC ADABRACADA]
  end

  %w[fegiach bfgiak hfdegi iakhfd fgiakhg].permutation.each do |permutation|
    ss *permutation, %w[bfgiakhgiakhfdegifegiach
                        bfgiakhgfegiachiakhfdegi
                        iakhfdegibfgiakhgfegiach
                        iakhfdegibfgiakhgfegiach
                        fegiachiakhfdegibfgiakhg
                        fegiachbfgiakhgiakhfdegi
                        iakhfdegifegiachbfgiakhg]
  end
end
于 2012-09-03T06:46:07.237 に答える