質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

解決済

2回答

2061閲覧

二つの文字列(文章)を比較し、一致する文字列を抽出する方法

emt501

総合スコア7

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

0グッド

0クリップ

投稿2016/11/05 08:40

###前提・実現したいこと
二つの文章を比較し、マッチする文字列を抜き出すアルゴリズムについて教えていただきたいです。

例:
文章A "ほげてすと、、、なむなむ"
文章B "hogehogeなむてすと"
→ "なむ","てすと"を抽出

文章の頭から一文字ずつ比較し、マッチした場合は続けて次の文字を比較...とやっていくことで抜き出せそうですが、比較回数かなり多くなってしまいます。
他に良い方法があれば教えていただきたいです。

初めての質問で至らぬ点もあるかもしれませんが、どうかご教授お願いします。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

こんにちは。

二つの文章を比較し、・・・

例:
文章A "ほげてすと、、、なむなむ"
文章B "hogehogeなむてすと"

とあったので、対象となる文章AとBは、日本語の文法規則に則った文章であると、問題を解釈しました。

その前提で、日本語で書かれた2つの文章に共通して現れる文字列を抽出するのであれば、
手順として、まず両方を形態素解析して単語に分解するのはいかがでしょうか?

形態素解析した結果を、プログラムの中でどのようなデータ構造として持つのかは、
何をやりたいのかによりますが、形態素解析によって単語に分解すれば、例えば、
「二つの文章に含まれる名詞だけを抽出したい」
といった要件にも、そんなに大変なプログラムを書かなくても応えられるのではないかと
思います。

以上参考になれば幸いです。

(※AとBが日本語の文法規則に則った文章とは限らないのであれば、上記の回答は意味がないので
無視してください。)

投稿2016/11/05 10:08

jun68ykt

総合スコア9058

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

emt501

2016/11/05 15:51

ご回答有難うございます。 実はTwitterの投稿を対象としており、正確な文法でない文章が多く存在します。 なので、ご提案いただいた形態素解析ですが今回のケースでは難しいかもしれません... せっかく回答していただいたのに申し訳ありません。私の説明不足でした。 ですが、別の機会でこのケースに該当する場合は参考にさせていただきたいと思います。
jun68ykt

2016/11/05 16:22

ご返信ありがとうございます。なるほどです。Twitterの投稿では正確な文章は期待できないですね。
guest

0

ベストアンサー

どっちがどっちに対しての比較かを推測していました。
Aに含まれるものをBからと解釈して。
無限ループ上で、先頭文字にポインター。
それから2文字以上の一致と2文字一致した場合の処理。
これは”なむ”の出力から。
ならば、まずBのポインターに一致する文字の検索。(先頭は’h’でAには存在せず)
Bのポインターを移動(インクリメント)してみる。
この場合は最終文字まで一致なし。
同様に処理すると’て’で一致が。
’てすと’までが一致し。一つ目の回答。(BのポインターとAのポインターの非一致までを繰り返す)
その後、再度!のポインターを先頭にして’な’まで同様の処理。
Aの’なむ’がBの’なむなむ’に一致する(2文字以上の一致)で処理終了。
ですね。

投稿2016/11/05 09:59

MasahikoHirata

総合スコア3747

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問