ナイツ関数（ボケの方） DouKaku?

入力した文章のところどころを言い間違えて出力する関数を実装してください。
（ナベアツ算を見てて思いつきました）

入出力の方法は標準入出力や引数・戻り値など、扱いやすい方法でかまいません。

文字単位でランダムに間違えても面白くないので、単語のリストから似た単語の候補を探すようにしてください。英単語でもＯＫです。単語のリストは参考ページからダウンロードしたものを加工して利用すると良いと思います。（４０００個あります）

結果がつまらなくても構いませんが、面白いボケをうむ工夫があると良いです。
※人が考えたボケは求めてませんよ！

入力の例として「どう書く？org」の前文をお借りしました。ご自分でヤホーで調べたりして手ごろな文章を見つけて下しあ。

see: 日本語単語リスト

＜入力例＞
ドウカク org ヘ ヨウコソ
コノ サイト ハ ダサレタ オダイ ヲ イカニ トクカ キソイアウ
 プログラマ ノ タメノ コロシアム デス
トウコウ ヲ タメシテ ミタイ カタ ハ テスト
トリアエズ ナガメテ ミタイ カタ ハ ゲンゴ ノ イチラン ガ オススメ デス

＜出力例＞
ドウモク org ヘ ヨウコソ
コノ ザレゴト ハ ダサレタ オダイ ヲ イワハダ トシシタ キソイアウ
 プログラマ ノ タチノミ コロシアム デス
トウコウ ヲ ハナシテ ミチノリ カタ ハ プリント
トリアエズ ナガメテ ミツリン カタ ハ ゲンゴ ノ キンラン ガ オススメ デス

Squeak Smalltalk で。

単語のリストから文字数が似ていて最初と最後の文字が一致するものをピックアップし、該当がないときは元の単語を、複数ある時はランダムにチョイスして出力しています。

| in wordList file |
in := 'ドウカク org ヘ ヨウコソ
コノ サイト ハ ダサレタ オダイ ヲ イカニ トクカ キソイアウ
プログラマ ノ タメノ コロシアム デス
トウコウ ヲ タメシテ ミタイ カタ ハ テスト
トリアエズ ナガメテ ミタイ カタ ハ ゲンゴ ノ イチラン ガ オススメ デス'.

wordList := OrderedCollection new.
#('25_10' '40_25' '55_40' '70_55') do: [:range |
    file := FileStream fileNamed: 'fam', range, '.txt'.
    file converter: (TextConverter newForEncoding: 'sjis').
    file wantsLineEndConversion: true.
    [file atEnd] whileFalse: [wordList addAll: (file nextLine subStrings: String tab)].
    file close].

World findATranscript: nil.

in linesDo: [:line |
    Transcript cr.
    (line subStrings: ' ')
        do: [:each |
            | foundWords |
            foundWords := wordList select: [:word |
                (word size - each size) abs <= 1 and: [
                    word first = each first and: [word last = each last]]].
            foundWords ifEmpty: [foundWords := foundWords copyWith: each].
            Transcript show: foundWords atRandom]
        separatedBy: [Transcript space]]

"=>
ドクヤク org ヘ ヨワミソ
コノ サトビト ハ ダサレタ オトガイ ヲ イトコニ トシワカ キュウロウ
プラズマ ノ タカドノ コロシアム デス
トクユウ ヲ タメシテ ミタイ カタ ハ テナント
トキワズ ナツバテ ミタイ カタ ハ ゲンゴ ノ イチミン ガ オツトメ デス "

ボケるのに「レーベンシュタイン距離( http://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2 )」を使ってみました。

入力はテキストファイルからで。

/*
 * NightsFormula.java
 *
 */
import java.io.*;
import java.util.*;

public class NightsFormula {
    
    private static final double _MINSimilarityRate = 0.51;
    
    public static void main(String[] args){
        
        String[] wordList = getWordList( new String[]{"fam25_10.txt","fam40_25.txt","fam55_40.txt","fam70_55.txt"});
        
        String[] srcList = getWordList(new String[]{"inputSample.txt"});
        
        if(wordList == null || srcList == null){
            System.out.println("word list or src list is NULL");
            return;
        }
        StringBuffer outb = new StringBuffer();
        for(int i = 0; i < srcList.length; i++){
            StringBuffer sb = new StringBuffer();
            sb.append(srcList[i]).append("\t");
            for(int j = 0; j < wordList.length; j++){
                double sr = getSimilarityRate(srcList[i], wordList[j]);
                if(sr >=_MINSimilarityRate){
                    sb.append(wordList[j]).append("\t");
                }
            }
            String[] cand = split(sb);
            String sc = cand[(int)(cand.length*Math.random())];
            outb.append(sc).append(" ");
        }
        System.out.println(outb.toString());
    }
    
    private static double getSimilarityRate(String str1, String str2){
        int ld = getLevenshteinDistance(str1, str2);
        int len = (str1.length() > str2.length() ? str1.length() : str2.length());
        double result = ((double)(len - ld) / len);
        return result;
    }
    
    private static int getLevenshteinDistance(String str1, String str2){
        
    int[][] lArr = new int[str1.length()+1][str2.length()+1];
        
    for(int i = 0; i < lArr.length; i++) lArr[i][0] = i;
    for(int i = 0; i < lArr[0].length; i++) lArr[0][i] = i;
    
    for(int i = 0; i < str1.length(); i++){
            for(int j = 0; j < str2.length(); j++){
                int cost = (str1.charAt(i) == str2.charAt(j)) ? 0 : 1;
                lArr[i+1][j+1] = getMinimum( lArr[i][j+1] +1, lArr[i+1][j] +1, lArr[i][j] +cost );
            }
    }
    return lArr[str1.length()][str2.length()];
    }
    
    private static int getMinimum(int a, int b, int c){
        int m = a < b ? a : b;
        return m < c ? m : c;
    }
    
    private static String[] getWordList(String[] filenames){
        FileReader fr = null;
        BufferedReader in = null;
        StringBuffer sb = new StringBuffer();
        for(int i = 0; i < filenames.length; i++){
            try{
                in = new BufferedReader(fr = new FileReader(filenames[i]));
                String line = null;
                while((line=in.readLine())!= null){
                    sb.append(line).append("\t");
                }
            }catch(Throwable t){
                t.printStackTrace();
                return null;
            }finally{
                if(in != null){ try{ in.close(); }catch(Throwable t){ ; }finally{ in = null;} }
                if(fr != null){ try{ fr.close(); }catch(Throwable t){ ; }finally{ fr = null;} }
            }
        }
        return split(sb);
    }
    
    private static String[] split(StringBuffer sb){
        StringTokenizer st = new StringTokenizer(sb.toString(), " \t");
        int len = st.countTokens();
        String[] wlist = new String[len];
        for(int i = 0; i < len; i++){
            wlist[i] = st.nextToken();
        }
        return wlist;
    }
}

元ネタがわからないので、外してたらすみません。

コード欄が1つなのでつなげていますが、mkdic.plとnaitsu.plの
2つのプログラムからなります。

mkdic.plは、事前にデータを作るプログラムです。
mecabのipadicのソースに含まれるNoun.csvをカレントディレクトリ
に置いて実行します。
Noun.csvにある60,477語の総当たり（3,657,407,052通り）で、
読みのLevenshtein距離が1になる組み合わせを求め、DB化します。

# 後から考えると、1操作で変換できる組み合わせだけを抜き出す
# （1操作以上は計算しない）のが効率的でしたが、それに気が
# ついたのは1日経過後ぐらい。

naitsu.plは、引数のファイルまたは標準入力から読み込んだ
テキストをText::MeCabで分解して、単語がmkdic.plで作った
DBにあればランダムに置きかえます。


$ perl mkdic.pl
（この間3〜4日ぐらい）
$ cat sample.txt
このサイトは出されたお題をいかに解くか競い合う、プログラマのためのコロシアムです。
$ perl naitsu.pl sample.txt
この細部は出されたお蛇尾をいかに解くか競い合う、プログラムのまめのコロシアムです。
$ perl naitsu.pl sample.txt
この最多は出されたおだてをいかに解くか競い合う、プログラマーのタネのコロシアムです。

#!/usr/bin/perl
# mkdic.pl
use strict;
use warnings;
use Encode;
use Text::Levenshtein qw(fastdistance);
use DBI;

my $source = './Noun.csv';
my $source_enc = 'euc-jp';

my $dbfile = './ls1.sqlite';
my $db_enc = 'utf-8';

sub readin {
    my @list;
    open my $fh, '<', $source or die;
    while (<$fh>) {
        my ($word, $yomi) = (split(/,/, decode($source_enc, $_)))[0, 11];
        push @list, { word => $word, yomi => $yomi };
    }
    close $fh;
    \@list;
}

sub make_db {
    my $dbh = shift;
    $dbh->do('CREATE TABLE ls1 (key string, val string)');
}

sub make_ls1 {
    my $dbh = shift;
    my $list_ref = shift;

    my @list = @{$list_ref};
    my $sth = $dbh->prepare('INSERT INTO ls1 VALUES (?,?)');
    while (@list) {
        my $word1 = shift @list;
        for my $word2 (@list) {
            if (fastdistance($word1->{yomi}, $word2->{yomi}) == 1) {
                my $word1_enc = encode($db_enc, $word1->{word});
                my $word2_enc = encode($db_enc, $word2->{word});
                $sth->execute($word1_enc, $word2_enc);
                $sth->execute($word2_enc, $word1_enc);
                print ("$word1_enc:$word2_enc\n");
            }
        }
    }
}

my $list_ref = readin();
unlink $dbfile if (-f $dbfile);
my $dbh = DBI->connect("dbi:SQLite:dbname=$dbfile", '', '',
                       { RaiseError => 1, AutoCommit => 0 });
make_db($dbh);
make_ls1($dbh, $list_ref);
$dbh->commit;
$dbh->disconnect();



#!/usr/bin/perl
# naitsu.pl
use strict;
use warnings;
use DBI;
use Text::MeCab;

my $dbfile = './ls1.sqlite';

sub get_ls1s {
    my ($sth, $word) = @_;
    $sth->execute($word);
    my ($word2) = $sth->fetchrow_array or return;
    return $word2;
}

my $text = do { local $/; <ARGV>; };

my $dbh = DBI->connect("dbi:SQLite:dbname=$dbfile", '', '',);
my $sth = $dbh->prepare(
    "SELECT val FROM ls1 WHERE key=? ORDER BY random() LIMIT 1" );

my $mecab = Text::MeCab->new();
my $node = $mecab->parse($text);

for (; $node; $node = $node->next) {
    my $word = $node->surface;
    if (my $naitsu = get_ls1s($sth, $word)) {
        print $naitsu;
    } else {
        print $word;
    }
}
print "\n";

$sth->finish;
undef $sth;
$dbh->disconnect;

　JavaとSmalltalkの投稿を参考に書いてみました。

#! /usr/bin/ruby -Ks

class LevenshteinDistance
    def self.distance(a, b)
        table = Array.new(a.split('').size + 1) do |i|
            i == 0 ? (0..b.split('').size).to_a : Array.new(b.split('').size).unshift(i)
        end
        (1..table.size - 1).each do |i|
            (1..table[i].size - 1).each do |j|
                table[i][j] = [
                        table[i - 1][j] + 1,
                        table[i][j - 1],
                        table[i - 1][j - 1] + (a.split('')[i - 1] == b.split('')[j - 1] ? 0 : 1)
                    ].min
            end
        end
        table.last.last
    end
end

class Knights
    attr_accessor :dictionary
    def initialize(dict_file)
        self.dictionary = []
        File.open(dict_file) { |f| f.each { |line| self.dictionary.concat(line.split(/\s+/)) } }
        self
    end
    def translate(source)
        source.split(/\s+/).map do |w|
            list = self.dictionary.select { |d| yield(w, d) }.unshift(w)
            list[rand(list.size)]
        end
    end
end

source = <<EOS
ドウカク org ヘ ヨウコソ
コノ サイト ハ ダサレタ オダイ ヲ イカニ トクカ キソイアウ
プログラマ ノ タメノ コロシアム デス
トウコウ ヲ タメシテ ミタイ カタ ハ テスト
トリアエズ ナガメテ ミタイ カタ ハ ゲンゴ ノ イチラン ガ オススメ デス
EOS
knights = Knights.new("./path/to/word_list.txt")
puts "入力:\n#{source}"
puts "出力:"
source.each_line do |line|
    puts(
        knights.translate(line) do |w, d|
            LevenshteinDistance.distance(w, d).to_f / [w.split('').size, d.split('').size].sort.first < 0.4
        end.join(" ")
    )
end
puts "出力:"
source.each_line do |line|
    puts(
        knights.translate(line) do |w, d|
            (w.split('').size - d.split('').size).abs <= 1 && w.split('').first == d.split('').first && w.split('').last == d.split('').last
        end.join(" ")
    )
end

　レーベンシュタイン距離の計算処理に間違いがあったので修正したものを。

#! /usr/bin/ruby -Ks

class LevenshteinDistance
    def self.distance(a, b)
        table = Array.new(a.split('').size + 1) do |i|
            i == 0 ? (0..b.split('').size).to_a : Array.new(b.split('').size).unshift(i)
        end
        (1..table.size - 1).each do |i|
            (1..table[i].size - 1).each do |j|
                table[i][j] = [
                        table[i - 1][j] + 1,
                        table[i][j - 1] + 1,
                        table[i - 1][j - 1] + (a.split('')[i - 1] == b.split('')[j - 1] ? 0 : 1)
                    ].min
            end
        end
        table.last.last
    end
end

class Knights
    attr_accessor :dictionary
    def initialize(dict_file)
        self.dictionary = []
        File.open(dict_file) { |f| f.each { |line| self.dictionary.concat(line.split(/\s+/)) } }
        self
    end
    def translate(source)
        source.split(/\s+/).map do |w|
            (list = self.dictionary.select { |d| yield(w, d) }).empty? ? w : list[rand(list.size)]
        end
    end
end

source = <<EOS
ドウカク org ヘ ヨウコソ
コノ サイト ハ ダサレタ オダイ ヲ イカニ トクカ キソイアウ
プログラマ ノ タメノ コロシアム デス
トウコウ ヲ タメシテ ミタイ カタ ハ テスト
トリアエズ ナガメテ ミタイ カタ ハ ゲンゴ ノ イチラン ガ オススメ デス
EOS
puts "入力:\n#{source}"
puts "出力:"
knights = Knights.new("/path/to/wordlist.txt")
source.each_line do |line|
    puts(
        knights.translate(line) do |w, d|
            LevenshteinDistance.distance(w, d).to_f / [w.split('').size, d.split('').size].max < 0.5
        end.join(" ")
    )
end
puts "出力:"
source.each_line do |line|
    puts(
        knights.translate(line) do |w, d|
            (w.split('').size - d.split('').size).abs <= 1 && w.split('').first == d.split('').first && w.split('').last == d.split('').last
        end.join(" ")
    )
end

　Scalaで。

import    java.io.{File,FileInputStream,InputStreamReader,BufferedReader}
import    scala.util.Random

object LevenshteinDistance {
    def distance(a:String, b:String) = {
        var    t:List[List[Int]] = List.range(a.size, -1, -1).foldLeft(List[List[Int]]())(
            (r,i) => i match {
                case 0 => List.range(0, b.size + 1)::r
                case _ => (i::List.make(b.size, 0))::r
            }
        )
        1.to(t.size - 1).foreach(i =>
            1.to(t(i).size - 1).foreach(j =>
                t = t.take(i) ++
                    List(
                        t(i).take(j) ++
                        List(
                            (t(i - 1)(j) + 1)
                            .min(t(i)(j - 1) + 1)
                            .min(
                                t(i - 1)(j - 1) +
                                ((a(i - 1) == b(j - 1)) match { case true => 0; case _ => 1 })
                            )
                        ) ++
                        t(i).takeRight(t(i).size - j - 1)
                    ) ++
                    t.takeRight(t.size - i - 1)
            )
        )
        t.last.last
    }
}

class CKnights(f:String, e:String) {
    var    d:List[String] = List()
    val    i:BufferedReader = new BufferedReader(new InputStreamReader(new FileInputStream(f), e))
    val    r:Random = new Random
    while(i.ready) {
        val    l:String = i.readLine
        if (l != "") d = d:::l.split("\\s+").toList
    }
    i.close
    def translate(s:String)(j:(String,String)=>Boolean):List[String] =
        s.split("\\s+").foldRight(List[String]())((w,k) =>
            (d.filter(e => j(w, e)) match {
                case t if t.isEmpty => w
                case t => t(r.nextInt(t.size))
            })::k
        )
}

object Knights {
    def source:List[String] = readLine match {
            case null => List()
            case l => l::source
        }
    def main(args:Array[String]):Unit = args.size match {
            case a if a != 1 => println("usage: Knights DICTFILE")
            case _ => {
                var    s:List[String] = source
                var    k:CKnights = new CKnights(args.first, "Shift_JIS")
                println("入力:")
                s.foreach(l => println(l))
                println("出力:")
                s.foreach(l => println(
                        k.translate(l)((w, e) =>
                            LevenshteinDistance.distance(w, e).toFloat / w.size.max(e.size) < 0.5
                        ).mkString(" ")
                    )
                )
                println("出力:")
                s.foreach(l => println(
                        k.translate(l)((w, e) =>
                            Math.abs(w.size - e.size) <= 1 && w.first == e.first && w.last == e.last
                        ).mkString(" ")
                    )
                )
            }
        }
}

Java版でレーベンシュタイン距離を使っていたのに触発されたRuby版に触発されて、同じようなものを書いてみました。if-else式のために、Python2.5以上です。

Java版そのままだと、総あたり検索していて遅かったので、先頭文字が一致する単語のみに絞ることにしました。あと、候補が複数ある場合はランダムに選択するようにしています。

ちなみに単語辞書は毎回元サイトから拾っているので、オフラインでは動きません。

#!coding: utf-8
import urllib, random

def download_words():
    prefix = "http://www.ais.riec.tohoku.ac.jp/lab/wordlist/"
    files = ["fam70_55.txt", "fam55_40.txt", 
             "fam40_25.txt", "fam25_10.txt"]
    words = []
    for f in files:
        fd = urllib.urlopen(prefix + f)
        for line in fd:
            if line.strip() != "":
                words.extend(line.strip().decode("sjis").split("\t"))
        fd.close()
    return words

allwords = download_words()

def Levenshtein_distance(word0, word1):
    d = dict()
    for i in range(len(word0) + 1): d[(i,0)] = i
    for j in range(len(word1) + 1): d[(0,j)] = j
    for i in range(1, len(word0) + 1):
        for j in range(1, len(word1) + 1):
            cost = 0 if word0[i-1] == word1[j-1] else 1
            d[(i,j)] = min(d[(i-1,j)]+1, d[(i,j-1)]+1, d[(i-1,j-1)]+cost)
    return d[(len(word0), len(word1))]

def similarity(word0, word1):
    l = max(len(word0), len(word1))
    return float(l - Levenshtein_distance(word0, word1)) / l

def find_alt_word(word):
    alt_words = filter(
        lambda alt: alt[0] == word[0] and similarity(word, alt) > 0.5,
        allwords)
    )
    return random.choice(alt_words) if alt_words else word

def knights(text):
    return  u" ".join([find_alt_word(w) for w in text.split(u" ")])

print knights(u'''ドウカク org ヘ ヨウコソ
コノ サイト ハ ダサレタ オダイ ヲ イカニ トクカ キソイアウ
プログラマ ノ タメノ コロシアム デス
トウコウ ヲ タメシテ ミタイ カタ ハ テスト
トリアエズ ナガメテ ミタイ カタ ハ ゲンゴ ノ イチラン ガ オススメ デス'''
).encode("sjis")

なるべく面白くボケる様に調整してみましたが、その所為でマジックナンバー溢れるヘンなコードになってしまいました。

あと一々単語データ全部について編集距離を計算してるので、Ruby1.8.x系だと遅くてお話になりません。なんともはや……。

--

ドウヤク org ヘ ヨワミソ
コノ サイト ハ ダサレタ オダイ ヲ イチニン トクカ キソイアウ
プログラマ ノ タメノ コロシヤ デス
トウコウ ヲ タメシテ ミタイ カタ ハ テスト
トリアエズ ナガソデ ミタマヤ カタ ハ ゲンタツ ノ イモバン ガ オツトメ デス

if RUBY_VERSION >= "1.9"
  class Array
    def choice
      self[ rand(self.size) ]
    end
  end
end

def levenstein(a, b)
  ld = Array.new(a.size+1){ Array.new(b.size+1){0} }
  0.upto(a.size){|i|
    ld[i][0] = i
  }
  0.upto(b.size){|i|
    ld[0][i] = i
  }
  1.upto(a.size){|i|
    1.upto(b.size){|j|
      t = a[i-1] == b[i-1] ? 0 : 1
      ld[i][j] = [ld[i-1][j]+1, ld[i][j-1]+1, ld[i-1][j-1] + t].min
    }
  }
  return ld[-1][-1]
end

DIC = File.read("words.dat").encode("UTF-8").split(/\s+/m)

def knights(text)
  text.each_line.map{|ln|
    ln.split(" ").map{|wd|
      DIC.find_all{|w2| levenstein(wd, w2)*15/(wd.size+w2.size) < rand(6) && wd[0] == w2[0]}.choice || wd
    }.join(" ")
  }.join($/)
end

if $0 == __FILE__
  puts knights($<.read)
end

javaの解法を参考にさせていただきました。

#!/usr/bin/env groovy
final MIN_SIMILARITY_RATE = 0.51

def wordList = []
["fam25_10.txt", "fam40_25.txt", "fam55_40.txt", "fam70_55.txt"].each{
    Collections.addAll(wordList, new File(it).text.split(/\s/))
}
def file = new File("inputSample.txt")
assert wordList
assert file?.exists()

println file.text.replaceAll(/(?m)\S+/){ word ->
    def convertList = [ word, *wordList.findAll{ other ->
        getSimilarityRate(word, other) >= MIN_SIMILARITY_RATE
    } ]
    Collections.shuffle(convertList)
    convertList[0]
}

double getSimilarityRate(String str1, String str2){
    def len1 = str1.size()
    def len2 = str2.size()

    def matrix = new int[len1+1][len2+1]
    
    for(int i = 0; i < matrix.size(); i++){
        matrix[i][0] = i
    }
    for(int i = 0; i < matrix[0].size(); i++){
        matrix[0][i] = i
    }
    
    for(int i = 0; i < len1; i++){
        for(int j = 0; j < len2; j++){
            int cost = (str1[i] == str2[j]) ? 0 : 1
            matrix[i+1][j+1] = [matrix[i][j+1] +1, matrix[i+1][j] +1, matrix[i][j] +cost].min()
        }
    }
    
    def longer = [len1, len2].max()
    (longer - matrix[len1][len2])/longer
}

DouKaku?

ナイツ関数（ボケの方）

Posted feedbacks - Flatten

Index

Feed

Other

Link

Pathtraq