0

我正在研究 Ruby 中的字符串重建算法（动态编程示例中的经典，将空间较少的文本转换为正常间隔的文本）。下面的代码是纯 ruby​​ 的，你可以复制粘贴并立即开始测试，它在 80% 的时间内都在工作，而且字典越大越容易出错。我已经用超过 80k 个单词的词典对其进行了测试，但效果不太好，大约 70% 的时间。

如果字典中出现这个词，如果有办法让它 100% 工作，请告诉我。

这是代码：（它的间距很好，应该非常易读）

# Partially working string reconstruction algo in pure Ruby

# the dictionary
def dict(someWord)
  myArray = [" ", "best", "domain", "my", "successes", "image", "resizer", "high", "tech", "crime", "unit", "name", "edge", "times", "find", "a", "bargain", "free", "spirited", "style", "i", "command", "go", "direct", "to", "harness", "the", "force"]
  return !!(myArray.index(someWord))
end


# inspired by http://cseweb.ucsd.edu/classes/wi12/cse202-a/lecture6-final.pdf

## Please uncomment the one you wanna use
#
# (all the words used are present in the dictionary above)
#
# working sentences
  x = ' ' + "harnesstheforce"
# x = ' ' + "hightechcrimeunit"
#
# non working sentences
# x = ' ' + "findabargain"
# x = ' ' + "icommand"

puts "Trying to reconstruct #{x}"

# useful variables we're going to use in our algo
n = x.length
k = Array.new(n)
s = Array.new(n)
breakpoints = Hash.new
validBreakpoints = Hash.new

begin

  # let's fill k
  for i in 0..n-1
    k[i] = i
  end

  # the core algo starts here
  s[0] = true
  for k in 1..n-1

    s[k] = false

    for j in 1..k
      if s[j-1] && dict(x[j..k])
        s[k] = true

        # using a hash is just a trick to not have duplicates
        breakpoints.store(k, true)
      end
    end

  end

  # debug
  puts "breakpoints: #{breakpoints.inspect} for #{x}"

  # let's create a valid break point vector

  i=1
  while i <= n-1 do

    # we choose the longest valid word
    breakpoints.keys.sort.each do |k|

      if i >= k
        next
      end

      # debug: when the algo breaks, it does so here and goes into an infinite loop
      #puts "x[#{i}..#{k}]: #{x[i..k]}"
      if dict(x[i..k])
        validBreakpoints[i] = k
      end
    end

    if validBreakpoints[i]
      i = validBreakpoints[i] + 1
    end

  end

  # debug
  puts "validBreakpoints: #{validBreakpoints.inspect} for #{x}"

  # we insert the spaces at the places defined by the valid breakpoints
  x = x.strip
  i = 0
  validBreakpoints.each_key do |key|
    validBreakpoints[key] = validBreakpoints[key] + i
    i += 1
  end

  validBreakpoints.each_value do |value|
    x.insert(value, ' ')
  end

  puts "Debug: x: #{x}"


  # we capture ctrl-c
rescue SignalException
  abort

# end of rescue
end
4

1 回答 1

1

请注意，您的算法对于包含单字符单词的字符串会失败。这是一个错误的错误。您忽略了这些单词之后的断点，因此您最终得到了一个单词 ( "abargain") 不包含在您的字典中。

改变

   if i >= k
     next
   end

至

   if i > k
     next
   end

或更像Ruby

   next if i > k

另请注意，只要您的字符串包含不是单词的内容，您就会陷入无限循环：

if validBreakpoints[i]        # will be false 
  i = validBreakpoints[i] + 1 # i not incremented, so start over at the same position
end

您最好将此视为错误

return '<no parse>' unless validBreakpoints[i] # or throw if you are not in a function
i = validBreakpoints[i] + 1

问题"inotifier"在于您的算法存在缺陷。总是选择最长的词是不好的。在这种情况下，检测到的第一个“有效”断点位于 之后，"in"它会留下 non-word "otifier"。

于 2013-07-26T11:03:53.417 回答