java - 在字符串中搜索建议

Question

我有一个包含以下内容的文本文件:mariam amr sara john jessy salma mkkkkkaooooorllll

用户输入要搜索的词:例如:maram

如你所见，它在我的文本文件中不存在..我想给出建议，类似于单词maram是mariam

我使用了最长公共(public)子序列，但它给出了 mariam 和 mkkkkkaooooorllll 因为它们都包含最长公共(public)子序列“mar”

我只想强制选择mariam有什么想法吗？

提前致谢

/**
 ** Java Program to implement Longest Common Subsequence Algorithm
 **/

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

   /** Class  LongestCommonSubsequence **/
    public class  LongestCommonSubsequence
    {    
   /** function lcs **/
    public String lcs(String str1, String str2)
    {
    int l1 = str1.length();
    int l2 = str2.length();

    int[][] arr = new int[l1 + 1][l2 + 1];

    for (int i = l1 - 1; i >= 0; i--)
    {
        for (int j = l2 - 1; j >= 0; j--)
        {
            if (str1.charAt(i) == str2.charAt(j))
                arr[i][j] = arr[i + 1][j + 1] + 1;
            else 
                arr[i][j] = Math.max(arr[i + 1][j], arr[i][j + 1]);
        }
    }

    int i = 0, j = 0;
    StringBuffer sb = new StringBuffer();
    while (i < l1 && j < l2) 
    {
        if (str1.charAt(i) == str2.charAt(j)) 
        {
            sb.append(str1.charAt(i));
            i++;
            j++;
        }
        else if (arr[i + 1][j] >= arr[i][j + 1]) 
            i++;
        else
            j++;
    }


    return sb.toString(); 
   //read text file, if a word contains sb.toString() , print it


}

/** Main Function **/
public static void main(String[] args) throws IOException
{    
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    System.out.println("Longest Common Subsequence Algorithm Test\n");

    System.out.println("\nEnter string 1");
    String str1 = br.readLine();

    System.out.println("\nEnter string 2");
    String str2 = br.readLine();

    LongestCommonSubsequence obj = new LongestCommonSubsequence(); 
    String result = obj.lcs(str1, str2);

    System.out.println("\nLongest Common Subsequence : "+ result);
}

Answer 1

有一些像这样的模糊匹配技术——Apache Commons 提供了一些优秀的工具来比较两个字符串彼此的相似程度。查看 Levenshtein Distance 的 javadoc和 Jaro Winkler Distance计算方法。

使用 Levenshtein Distance，分数越低，字符串越相似:

StringUtils.getLevenshteinDistance("frog", "fog") == 1
StringUtils.getLevenshteinDistance("fly", "ant") == 3

您还可以考虑计算 Double Metaphone对于每个字符串 - 这将允许您确定这些字符串在说话时“听起来”有多相似，即使它们不一定拼写相似。

回到您的问题 - 使用这些工具，如果用户的搜索词在文本文件中任何字符串的特定阈值内，您可以提出建议。