3

文章の一部を縦に読んだり横に読んだりすると、ある言葉が見つかることがあります。
このことをより一般的に次のように考えることにします。

①文章(縦書きと横書きがありますが、ここでは横書きとします。)を
 x×y行列に文字がおさまったもののように扱う。
②行列の任意の場所から出発し、一つ右もしくは一つ下の文字をたどっていく。
 注)縦読みや横読みを含んでいますが、斜めに読むことは含んでいません。

さて、指定した文字列が見つかれば、
"I found it!"
を出力し、見つからなければ、
"Not found"
を出力するものとします。

次に示すコードでは、
出発点から一つずつ順番に指定した文字列と一致する文字を探している
のですが、
xが大きくなっても指定された文字列を高速に探し出せるようにするには
どうすればよろしいでしょうか?

# -*- coding: cp932 -*-

x = 10
y = 11
@num = (0..x * y - 1).to_a
# x×y行列(ただしy列目は番兵をおく)
ary1 = [
'あ', 'か', 'ま', 'き', 'が', 'み', 'ま', 'き', 'ま', 'き', '番兵',
'あ', 'か', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', '番兵',
'か', 'ま', 'ま', 'が', 'あ', 'か', 'ま', 'あ', 'ま', 'み', '番兵',
'あ', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', 'み', '番兵',
'き', 'か', 'ま', 'あ', 'お', 'か', 'ま', 'あ', 'み', 'き', '番兵',
'あ', 'か', 'ま', 'あ', 'ま', 'き', 'ま', 'あ', 'き', 'あ', '番兵',
'か', 'ま', 'き', 'あ', 'あ', 'か', 'ま', 'あ', 'ま', 'あ', '番兵',
'あ', 'か', 'が', 'あ', 'あ', 'か', 'ま', 'あ', 'き', 'あ', '番兵',
'あ', 'か', 'み', 'あ', 'あ', 'か', 'ま', 'あ', 'が', 'み', '番兵',
'あ', 'か', 'ま', 'お', 'ま', 'き', 'が', 'み', '。', ' ', '番兵'
]
# ary1を一文字変更
ary2 = [
'あ', 'か', 'ま', 'き', 'が', 'み', 'ま', 'き', 'ま', 'き', '番兵',
'あ', 'か', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', '番兵',
'か', 'ま', 'ま', 'が', 'あ', 'か', 'ま', 'あ', 'ま', 'み', '番兵',
'あ', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', 'み', '番兵',
'き', 'か', 'ま', 'あ', 'お', 'か', 'ま', 'あ', 'み', 'き', '番兵',
'あ', 'か', 'ま', 'あ', 'ま', 'き', 'ま', 'あ', 'き', 'あ', '番兵',
'か', 'ま', 'き', 'あ', 'あ', 'か', 'ま', 'あ', 'ま', 'あ', '番兵',
'あ', 'か', 'が', 'あ', 'あ', 'か', 'ま', 'あ', 'き', 'あ', '番兵',
'あ', 'か', 'み', 'あ', 'あ', 'か', 'ま', 'あ', 'が', 'ま', '番兵',
'あ', 'か', 'ま', 'お', 'ま', 'き', 'が', 'み', '。', ' ', '番兵'
]
ary3 = [
'あ', 'か', 'ま', 'き', 'が', 'み', 'ま', 'き', 'ま', 'き', '番兵',
'あ', 'か', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', '番兵',
'か', 'ま', 'ま', 'が', 'あ', 'か', 'ま', 'あ', 'ま', 'み', '番兵',
'あ', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', 'み', '番兵',
'き', 'か', 'ま', 'あ', 'お', 'ま', 'き', 'が', 'み', 'き', '番兵',
'あ', 'か', 'ま', 'あ', 'ま', 'き', 'が', 'あ', 'き', 'あ', '番兵',
'か', 'ま', 'き', 'あ', 'あ', 'が', 'み', 'き', 'ま', 'あ', '番兵',
'あ', 'か', 'が', 'あ', 'あ', 'み', 'き', 'ま', 'き', 'あ', '番兵',
'あ', 'か', 'み', 'あ', 'あ', 'か', 'ま', 'き', 'が', 'ま', '番兵',
'あ', 'か', 'ま', 'お', 'ま', 'き', 'が', 'が', '。', ' ', '番兵'
]

def search(ary, i, str_ary, str)
  i_ary = []
  str_ary.each{|m|
    # strを右と下から探す
    ([m + 1, m + i] & @num).each{|n|
      i_ary.push(n) if ary[n] == str
    }
  }
  i_ary
end

def find_the_word(ary, i, str)
  str_size = str.size
  message = 'Not found'
  @num.each{|x|
    if ary[x] == str[0]
      s = 1
      next_a = search(ary, i, [x], str[s])
      while next_a.size > 0 && s < str_size - 1
        a = next_a
        s += 1
        next_a = search(ary, i, a, str[s])
      end
      if next_a.size > 0 && s == str_size - 1
        message = 'I found it!'
        break
      end
    end
  }
  message
end

p 'ary1'
p find_the_word(ary1, y, 'あかまきがみあおまきがみきまきがみ')
p 'ary2'
p find_the_word(ary2, y, 'あかまきがみあおまきがみきまきがみ')
p 'ary3'
p find_the_word(ary3, y, 'あかまきがみあおまきがみきまきがみ')

出力結果
"ary1"
"I found it!"
"ary2"
"Not found"
"ary3"
"Not found"

(追記)
「xが大きくなっても指定された文字列を高‌​速に探し出せるようにする」とありますが、具体的にどれくらいの大きさのものをどれくらいのスピードで探し出したいのか、具体的なゴールはありますか?
に対する回答ですが、
xが1000位でも必ず1秒以内で結果が出力される
ように変更したいです。
現状だと、(x = 1010 に変更し、)
ary2を100回繰り返したものにary1を加えたものに対して、
"I found it!"と表示されるまで1秒もかからないのに対し、
ary3を100回繰り返したものにary1を加えたものに対して、
"I found it!"と表示されるまで何分も待たないといけません。

4
  • 1
    すいません、ary1がなぜfoundになり、ary2がなぜnot foundになるのか、理屈がよくわかりませんでした。ary1とary2の何をどう見るとfound/not foundが決まるのでしょうか?もうちょっと具体的に教えてください。(もしくはもっとシンプルな例で教えてください)また、「xが大きくなっても指定された文字列を高速に探し出せるようにする」とありますが、具体的にどれくらいの大きさのものをどれくらいのスピードで探し出したいのか、具体的なゴールはありますか? Commented 2015年9月19日 22:21
  • @Junichi Ito 縦読みや横読みのように、ary1には「あかまきがみあおまきがみきまきがみ」という文字列が隠されています。例えば、ary1[11]から出発して、ary1[1‌​2],ary1[23],ary1[34],ary1[35],ary1[36],…,ary1[97]と辿れば指定した文字列が見つかります。一方、ary2はどの場所から‌​出発し、どのように縦横(右と下)動いても指定した文字列は見つかりません。
    – TOM
    Commented 2015年9月20日 4:08
  • @Junichi Ito 具体的な目標について追記しました。
    – TOM
    Commented 2015年9月20日 4:08
  • 1
    dpタグですが、英語版でもdynamic-programmingですし、日本語版なら「動的計画法」がいいのではと思います。それはそれとして、解の一つが動的計画法を使ったものであったというだけで、動的計画法を前提とした質問というわけではないように思うのですが・・・。
    – unarist
    Commented 2016年2月21日 12:38

2 件の回答 2

3

動的計画法でどうでしょう。

# -*- coding: utf-8 -*-

W = 11
ARY1 = # 出題のary1
ARY2 = # 出題のary2
ARY3 = # 出題のary3

def left(pos)
    pos - 1
end

def above(pos)
    pos - W
end

def union(a, b)
    (a + b).uniq
end

def dpsearch(ary, str)
    ss = Array.new(ary.size, [].freeze)
    last = str.size - 1

    W.upto(ary.size - 1) do |pos|
        pre = union(ss[left(pos)], ss[above(pos)]) + [-1]
        ss[pos] = pre.map { |s| s+1 }.select { |s| ary[pos] == str[s] }
        return pos if ss[pos].include? last
    end

    nil
end

[ARY1, ARY2, ARY3, ARY2 * 100 + ARY1, ARY3 * 100 + ARY1].each { |ary|
    ary = Array.new(W, '番兵') + ary # 番兵行を上に追加
    pos = dpsearch(ary, 'あかまきがみあおまきがみきまきがみ')
    if pos
        puts "Found (last char #{ary[pos]} at #{pos % W}, #{pos / W - 1})"
    else
        puts "Not found"
    end
}

出力結果はこうなります:

Found (last char み at 9, 8)
Not found
Not found
Found (last char み at 9, 12)
Found (last char み at 9, 1008)
1
  • [ARY1, ARY2, ARY3, ARY2 * 1000 + ARY1, ARY3 * 1000 + ARY1]に変更してもすぐに求まりますね。すごいです!
    – TOM
    Commented 2015年9月20日 15:11
0

上手く実装できていないのですが、次のような考え方で高速化できそうです。

①ある程度意味を持つ文字列※を探すので、指定された文字列の中に
 使用頻度の少ない文字があるはずなので、その文字を探す。
 ※指定された文字列が「おらおらおらおらおら」のようなものではないとする。

②行列の中から、使用頻度の少ない文字を見つけ、
 その前の文字を左と上から、その後の文字を右と下から
 探していく。

質問の例だと、「か」(または「お」)を行列の中から見つけ、
その前の文字「あ」が左または上にあるか、その後の文字「ま」が右または下にあるか
調べていくことになる。

(上記アルゴリズムの弱点)
行列に使用頻度の少ない文字が多数含まれている場合、あまり有用ではない。

1
  • 元データ自体から検索する方法ではどうしてもO(n)のオーダーになるのでは
    – pgrho
    Commented 2015年9月20日 4:41

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。