問題の説明#
n 個の長さ m の文字列配列と長さ m のターゲット文字列が与えられたとき、文字列配列の中でターゲット文字列と同じ文字列のインデックスを取得するプログラムを作成します。
例：
String[] toFind = new String[]{"abca","abab","abba","abca"};
String target = "abca";
// 結果 [0,3]
解決方法#
繰り返し処理#
最も簡単な方法は、文字列配列を繰り返し処理し、ターゲット文字列と比較して、ターゲット文字列と等しい場合はそのインデックスを結果に追加し、最後に結果を返します。
List<Integer> result = new ArrayList<>();
for (int i = 0; i < toFind.length; i++) {
if (target.equals(toFind[i])) {
result.add(i);
}
}
return result;
トライ木#
検索する文字列配列を使用してトライ木を構築し、根ノードにその文字列のインデックスを保存します。ターゲット文字列をトライ木に検索して結果を得ます。
図示#
コード実装#
class Main {
public static void main(String[] args) {
String[] toFind = new String[] { "abca", "abab", "abba", "abca" };
String target = "abca";
TrieTreeNode root = new TrieTreeNode();
for (int i = 0; i < toFind.length; i++) {
root.addStringToTree(toFind[i], i);
}
System.out.println(root.searchInTree(target));
}
}
// トライ木ノードの簡単な実装
class TrieTreeNode {
// 子ノード
private List<TrieTreeNode> list;
// インデックスを保存
private List<Integer> result;
// このノードの文字
private char ch;
// 空のコンストラクタ（根ノードを構築）
public TrieTreeNode() {
}
// 子ノードを構築
private TrieTreeNode(char ch) {
this.ch = ch;
}
// このノードの文字がchと等しいかを判断
private boolean isChar(char ch) {
if (this.ch == ch) {
return true;
}
return false;
}
// 文字がchの子ノードを取得（chの子ノードがない場合は自動的に追加）
private TrieTreeNode getNext(char ch) {
if (list == null) {
list = new ArrayList<>();
}
for (var item : list) {
if (item.isChar(ch)) {
return item;
}
}
var tmp = new TrieTreeNode(ch);
list.add(tmp);
return tmp;
}
// 上述のprivate関数を使用して文字列をトライ木に追加
public void addStringToTree(String str, int index) {
var tmp = this;
for (var item : str.toCharArray()) {
tmp = tmp.getNext(item);
}
if (tmp.result == null) {
tmp.result = new ArrayList<>();
}
tmp.result.add(index);
}
// トライ木でターゲット文字列を検索
public List<Integer> searchInTree(String target) {
var tmp = this;
for (var item : target.toCharArray()) {
if (tmp.list == null || tmp.list.isEmpty()) {
return new ArrayList<Integer>();
}
tmp = tmp.getNext(item);
}
return tmp.result;
}
}
ハッシュテーブル#
String->List<Integer>のハッシュテーブルを使用し、文字列をキーとして、対応するインデックスを値とします。直接テーブルを参照して結果を返します。
Map<String, List<Integer>> map = new HashMap<>();
for (int i = 0; i < toFind.length; i++) {
if (map.get(toFind[i]) == null) {
map.put(toFind[i], new ArrayList<Integer>());
}
map.get(toFind[i]).add(i);
}
return map.get(target);
文字列を切り分けた後にハッシュテーブルを使用（宿題）#
説明#
与えられた文字列が長すぎる場合、ハッシュテーブルを直接使用すると多くのスペースが無駄になります。この場合、文字列を切り分け、各サブストリングをキーとして、文字列のインデックスとサブストリングの位置からなる二元組リスト（<i,j>）を値とします。
ターゲット文字列を検索する際も、同様にターゲット文字列を切り分け、各サブストリングをキーとして二元組リストを取得します。もし二元組リストの中のある二元組（<i,j>）のサブストリング位置（j）がターゲット文字列内の現在のサブストリングの位置と同じであれば、toFind [i] のそのサブストリングがターゲット文字列と同じであることを示し、i をそのサブストリングのインデックス集合に追加します。最後にターゲット文字列のすべてのフィールドのインデックス集合の共通部分を求めて結果を得ます。
結果の各要素 i について、toFind [i] のすべてのサブストリングがターゲット文字列の対応するサブストリングと同じである。すなわち、toFind [i] はターゲット文字列と同じである。
図示#
コード実装（入力出力を含む、上記の String [] は List<String> に置き換え）#
import java.util.List;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.Map;
class Main {
public static void main(String[] args) {
// 入力する検索対象の文字列
List<String> list = new ArrayList<>();
String target;
try (var scanner = new Scanner(System.in)) {
System.out.print("ターゲット文字列を入力してください:");
// ターゲット文字列
target = scanner.nextLine();
System.out.println("検索する文字列配列を入力してください（スペースで終了）:");
String tmp;
// 非空の場合はlistに読み込む
while (!"".equals(tmp = scanner.nextLine())) {
list.add(tmp);
}
}
// 検索結果を出力
System.out.println(find(target, getMap(list)));
}
// 文字列分割関数
private static List<String> split(String src, int size) {
List<String> result = new ArrayList<>();
int begin = 0;
while (begin < src.length()) {
// 開始位置に切断長を加えたものが元の文字列の長さを超えた場合、文字列の末尾まで切断し、ループを抜ける
if (begin + size > src.length()) {
result.add(src.substring(begin));
break;
}
result.add(src.substring(begin, begin + size));
begin += size;
}
return result;
}
private static Map<String, List<Pair>> getMap(List<String> list) {
Map<String, List<Pair>> map = new HashMap<>();
for (int i = 0; i < list.size(); i++) {
String item = list.get(i);
// 検索する文字列を分割してList<String>を取得
var array = split(item, 10);
// すべての分割結果を繰り返し処理
for (int j = 0; j < array.size(); j++) {
String key = array.get(j);
// 分割結果をキーとしてmapから値を取得し、空であれば空のListを追加
if (map.get(key) == null) {
map.put(key, new ArrayList<Pair>());
}
// Listに二元組<i,j>（iは検索対象文字列の番号、jはその文字列内の位置）を追加
map.get(key).add(new Pair(i, j));
}
}
return map;
}
private static Set<Integer> find(String target, Map<String, List<Pair>> map) {
// targetが空の場合は空の集合を返す
if (target == null) {
return new HashSet<Integer>();
}
List<Set<Integer>> list = new ArrayList<>();
// 検索する文字列を分割
var array = split(target, 10);
// 分割された文字列配列を繰り返し処理
for (int i = 0; i < array.size(); i++) {
var key = array.get(i);
// この分割段で一致する行数の集合
Set<Integer> set = new HashSet<>();
// この段が一致する場合、行数をsetに追加
for (var item : map.get(key)) {
if (item.getLast() == i) {
set.add(item.getFirst());
}
}
// setをlistに追加
list.add(set);
}
// listが空の場合は空の集合を返す
if (list.isEmpty()) {
return new HashSet<Integer>();
}
// listの最初の集合を取得
Set<Integer> result = list.get(0);
// その集合をすべての集合に対して共通部分を取る
for (var item : list) {
result.retainAll(item);
}
// 結果を得て返す
return result;
}
}
// 簡単なPairの実装（<Integer,Integer>）
class Pair {
private final Integer first;
private final Integer last;
public Pair(Integer first, Integer last) {
this.first = first;
this.last = last;
}
public Integer getFirst() {
return this.first;
}
public Integer getLast() {
return this.last;
}
@Override
public boolean equals(Object compare) {
if (compare == null) {
return false;
}
Pair tmp = (Pair) compare;
if (this.first == tmp.first && this.last == tmp.last) {
return true;
}
return false;
}
}
さらなる考察（宿題）#
上記のアルゴリズムでは、固定長で検索領域toFindと検索対象targetを切り分けていますが、この方法では、特定のサブストリングが過度に頻繁に出現する可能性があります。したがって、文字列分割アルゴリズムを最適化し、出現頻度が高すぎる文字列を順延（つまり、そのサブストリングの後の文字をそのサブストリングの後に結合する）することを検討できます。以下に例を示します。
// 長さ3でこの文字列を切り分ける
"abcedfabcqweabcertabctyu"
// 得られた結果、abcが頻繁に出現することがわかり、そのため順延を行う
"abc|edf|abc|qwe|abc|ert|abc|tyu"
// 順延後、abcはabce|abcq|abctに分化し、このサブストリングの出現頻度を低下させました
"abce|edf|abcq|qwe|abce|ert|abct|tyu"
アルゴリズムの注意点#
-
「頻度が高すぎる」とはどう定義するか？
明らかに、許可されるサブストリングの最大出現頻度を示す比率を設定する必要があります。この閾値を超える出現頻度のサブストリングがある場合、そのサブストリングを順延し、出現頻度を低下させることを試みます。このプロセスを繰り返して、最終的に「すべてのサブストリングの出現頻度がこの閾値を下回る」結果を得ます。
-
文字列切り分けアルゴリズムの全体性。
この問題では、検索領域の各文字列とターゲット文字列を同じルールで切り分け、対応する位置を比較し、最後に対応する位置が等しい行数の共通部分を取得する方法を使用しています。
固定長で切り分ける場合、すべての文字列を個別に処理できます。しかし、現在のアルゴリズムフレームワークでは、文字列を個別に処理すると、切り分け方法が統一されない可能性があります。したがって、サブストリングの出現頻度の統計、サブストリングの順延などの操作を行う際には、{検索領域、検索対象} という文字列の集合を全体として扱い、すべての操作が検索領域内の各文字列とターゲット文字列に成功裏に作用することを保証する必要があります。
私の Java コード実装（再帰を使用し、複雑度が高い）#
import java.util.*;
class Main {
// サブストリングの順延に必要な長さを全体的に統計するためのグローバルカウント
private static Map<String, Integer> globalCount = new HashMap<>();
// 各切り分けでサブストリングの出現回数を統計するためのカウント
private static Map<String, Integer> count = new HashMap<>();
public static void main(String[] args) {
String[] range = new String[] { "abcabcedf", "abeabeefg", "bcdbcabec" };
String target = "abcabcedf";
// targetとrangeの切り分け方法は同じであるべきなので、同時に処理する必要があります
List<List<String>> list = cutStrings(range, target, 3, 0.2);
System.out.println(list);
}
// 切り分けたリストを取得する関数、引数は検索領域、検索対象、切り分けの元の長さ、サブストリングの最大出現頻度
private static List<List<String>> cutStrings(String[] range, String target, int width, double pro) {
// 総サブストリング数は（文字列の長さ/切り分けの長さ）を切り上げて、文字列の数を掛けたもの
int totalCount = ((int) Math.ceil((double) target.length() / width)) * (range.length + 1);
// 最大出現頻度が（1/総サブストリング数）未満の場合は不可能な状況であり、この場合は空の二次元配列を返す
// （制限を設けたが、特定の状況でproを低く設定しすぎるとstack overflowが発生する可能性がある）
if (pro < 1.0 / totalCount) {
return new ArrayList<List<String>>();
}
count.clear();
List<List<String>> result = new ArrayList<>();
// 検索領域を繰り返し処理し、指定された長さで文字列を切り分ける
for (var item : range) {
result.add(cutString(item, width));
}
// 指定された長さで検索対象を切り分ける
result.add(cutString(target, width));
// すべての文字列を切り分けた後、count内でサブストリングの出現回数を得た
// 次に、countを繰り返し処理し、制限頻度を超えるサブストリングをマークし、次回の切り分け時にそのサブストリングを順延する
boolean flag = false; // flagは制限を超える出現頻度の文字列があるかどうかを示す
for (var item : count.entrySet()) {
if ((double) item.getValue() / totalCount > pro) {
addForGlobalCount(item.getKey().substring(0, width));
flag = true;
}
}
// すべてのサブストリングの出現頻度が制限未満であれば、要求を満たし、直接返す
if (!flag) {
return result;
}
// そうでなければ、再度切り分けを行う
return cutStrings(range, target, width, pro);
}
// strの出現回数を統計
private static void addForCount(String str) {
if (count.get(str) != null) {
count.put(str, count.get(str) + 1);
} else {
count.put(str, 1);
}
}
// サブストリングが順延する必要がある長さを統計（基本的なロジックは、順延後も出現頻度が高い場合はさらに順延する）
private static void addForGlobalCount(String str) {
if (globalCount.get(str) != null) {
globalCount.put(str, globalCount.get(str) + 1);
} else {
globalCount.put(str, 1);
}
}
// strを切り分け、すべてのサブストリングの出現回数を統計（切り分け方法は毎回globalCountによって調整され、正しい結果に近づく）
private static List<String> cutString(String str, int width) {
List<String> result = new ArrayList<>();
int start = 0;
String sub;
while (start < str.length()) {
// 終了に達した場合は末尾まで切り分ける
if (start + width > str.length()) {
sub = str.substring(start);
result.add(sub);
addForCount(sub);
break;
}
Integer extraWidth;
// 順延が必要かどうかを判断
if ((extraWidth = globalCount.get(str.substring(start, start + width))) != null) {
// 順延が必要な場合、順延後に終了に達するかどうかを判断
int tmp = start + width + extraWidth > str.length() ? str.length() : start + width + extraWidth;
sub = str.substring(start, tmp);
} else {
sub = str.substring(start, start + width);
}
result.add(sub);
addForCount(sub);
start += width;
}
return result;
}
}