在arraylist中查找一个字符串的松散匹配

我有一个巨大的数组列表，其中包含1000个条目，其中一个条目是“world”。而且，我有一个词“大世界”。我想在数组列表中找到与“世界”相匹配的“大世界”一词。在arraylist中查找一个字符串的松散匹配

什么是最具成本效益的方法呢？我不能使用数组列表的方法。如果我遍历所有1000个条目并按照模式匹配它们，那么在性能方面将会非常昂贵。我为此使用Java。

请让我知道这是最好的方法是什么？

干杯， Ĵ

来源

2010-06-28 Abhishek

定义 “松散” 的比赛。一个字符串是否必须是其他字符的子字符串？ “心脏”和“耳朵”会匹配吗？这些会是英文单词/短语吗？如果我们要求你摆脱ArrayList，你能够吗？ – 2010-06-28 02:58:01

是的你的权利！ “心脏”一词与“耳朵”相匹配。我很灵活地使用任何种类的数据结构！ – Abhishek 2010-06-28 03:15:24

更多说明：1000个字符串是否是静态的？你想怎么做子串匹配？给定一个单词U，你想在数组列表中找到一个单词V，使得V是U的一个子串？如果U是某个其他V'的子串，那也是一个匹配吗？ – 2010-06-28 14:18:07

您可以分割了ArrayList的每一个元素进言，当你找到他们，就立即停止。

我想通过您的个人资料，你用Java开发，使用Lucene，你会很容易地做这样的事情

public class NodesAnalyzer extends Analyzer { 
    public TokenStream tokenStream(String fieldName, Reader reader) { 

     Tokenizer tokenizer = new StandardTokenizer(reader) 
     TokenFilter lowerCaseFilter = new LowerCaseFilter(tokenizer) 
     TokenFilter stopFilter = new StopFilter(lowerCaseFilter, Data.stopWords.collect{ it.text } as String[]) 
     SnowballFilter snowballFilter = new SnowballFilter(stopFilter, new org.tartarus.snowball.ext.ItalianStemmer()) 

     return snowballFilter 
    } 
} 

    Analyzer analyzer = new NodesAnalyzer() 

    TokenStream ts = analyzer.tokenStream(null, new StringReader(str)); 
    Token token = ts.next() 

    while (token != null) { 
     String cur = token.term() 
     token = ts.next(); 
    }

注：这是我从一个个人项目复制的，所以你将不得不转换的东西Groovy代码像Data.stopWords.collect{ it.text } as String[]与普通的Java

来源

2010-06-28 02:58:56 Jack

Lucene将会非常适合这种情况，尤其是当它超过1000字时。 – bwawok 2010-06-28 03:09:39

嗨，杰克，示例代码使用Lucene？ – Abhishek 2010-06-28 03:18:49

我贴的那个？是.. – Jack 2010-06-28 10:40:50

假设你不知道ArrayList中元素的含量。你将不得不遍历整个数组列表。

遍历arraylist会花费你O（n）。

排序ArrayList中难道不帮你，因为你都在谈论一组字符串的搜索字符串。而且仍然分拣会更昂贵。 O（nlogn）

来源

2010-06-28 02:49:57 DarthVader

如果必须反复搜索列表，则可以使用Collections的sort()和binarySearch()方法。

附录：正如@ user177883指出的，的O成本（N log n）的排序应防止后续O（log n）的搜索的利益进行权衡。

单词“心脏”匹配[单词]“耳朵”。

为完全匹配是不够的，这种做法是不够的。

来源

2010-06-28 02:57:11 trashgod

排序将比搜索更昂贵。 – DarthVader 2010-06-28 03:00:19

我可以做到这一点，但如果你看到binarySearch写入返回完全匹配。虽然我可能会编写一个定制的比较器，但可能很难确定一个松散匹配。 – Abhishek 2010-06-28 03:05:38

您如何知道用户是否希望在用户找到该值时停止。用户想要查找所有字符串的出现。那么你将不得不雇用许多二进制搜索。每次发现事件时，都会从adt中删除它，然后再执行另一个二进制搜索，最糟糕的情况是您最终可能会执行n个二进制搜索。你最糟糕的情况是2nlogn。与顺序搜索相比，这非常有效。 – DarthVader 2010-06-28 03:12:27

使用我有一个非常类似的问题。

使用此if/else if声明解决了这个问题。

if (myArrayList.contains(wordThatIsEntered) 
    && wordThatCantBeMatched.equals(wordThatIsEntered)) { 

    Toast.makeText(getApplicationContext(), 
    "WORD CAN'T BE THE SAME OR THAT WORD ISN'T HERE", 
    Toast.LENGTH_SHORT).show(); 
} 

else if (myArrayList.contains(wordThatIsEntered)) { 

    Toast.makeText(getApplicationContext(), 
    "FOUND THE EXACT WORD YOU ARE LOOKING FOR!", 
    Toast.LENGTH_SHORT).show(); 
}

来源

2014-07-14 14:31:30 Michael

在arraylist中查找一个字符串的松散匹配

回答

相关问题