如何从 ios 中的输入字符串中搜索所有单词？

Question

说，我有词汇量（大约 100000 个单词）和单词 ("inputstring")。所以：

我需要从 "inputstring" 生成所有单词，例如 "input"、"string"、"put"、"strinpg" 等。然后我需要检查它们我的词汇。你能说出什么好的算法吗？因为我只知道：

在第1步递归搜索所有可能的组合
使用 NSPredicates 在我的词汇表中过滤它们。

Answer 1

不知道有没有专门的算法可以解决你的问题。但是如果你必须用核心数据获取请求来解决它，可能性是有限的。我会这样做：

- (NSArray *)getWordsFromString:(NSString *)input{

   NSMutableArray *result = [NSMutableArray new];
   NSUInteger *startIndex = 0;

   for (NSUInteger i = 0; i < input.length ; i++){
       NSString *substring = [input substringWithRange:NSMakeRange(*startIndex, i)];

      NSPredicate *predicate = [NSPredicate predicateWithFormat:@"word == %@", substring]; 
      NSFetchRequest *fetchRequest = [NSFetchRequest fetchRequestWithEntityName:@"Word"];
      fetchRequest.predicate = predicate
      [fetchRequest setIncludesPropertyValues:NO];
      [fetchRequest setIncludesSubentities:NO];
      NSArray *fetchResult = fetch result with predicate

       if (fetchResult.count > 0){
           [result addObject:substring];
           startIndex = i;
       }
   } 

   return result;
}

Answer 2

听起来你想把你的词汇表插入到 trie 中。这将为您提供一个数据结构，然后您可以快速检查该数据结构以找到您的输入中存在于您的词汇表中的所有子字符串。

假设您只构建一次 trie 并检查大量不同的输入字符串，这将比从组合查找输入的所有子字符串开始快得多。（这种速度是以 trie 的内存为代价的。）

Answer 3

我尝试使用 NSRegularExpression，因为 CoreData 和 NSPredicate 似乎可以管理它们，但我无法找到可行的解决方案（可能与我在 Regex 方面的专业知识无关，但可能是一个线索).我也试过 NSCharacterSet，但它不能说出现的次数是正确的..

这可能不是更性感的方式，但是，您可以这样做：

NSString *searchedWord = @"inputString";

NSPredicate *predicate = [NSPredicate predicateWithBlock:^BOOL(NSString *evaluatedObject, NSDictionary *bindings) {
    for (NSUInteger index = 0; index < [evaluatedObject length]; index++)
    {
        NSString *subString = [evaluatedObject substringWithRange:NSMakeRange(index, 1)];

        NSUInteger numberOfOccurrencesInSearchWord = [self occurrencesOfSubString:subString inString:searchedWord];
        NSUInteger numberOfOccurrencesInCurrentWord = [self occurrencesOfSubString:subString inString:evaluatedObject];
        if (numberOfOccurrencesInCurrentWord > numberOfOccurrencesInSearchWord)
            return FALSE;
    }
    return TRUE;
}];

//Apply this predicate to your fetch

我将 occurrencesOfSubString:inString: 放在 class 中，但它可能是 NSString 上的类别。如果您更喜欢 NSRegularExpression，您也可以使用 rangeOfString:option:range 循环。 Source of the code（稍作修改）

-(NSUInteger)occurrencesOfSubString:(NSString *)subString inString:(NSString *)string
{
    NSUInteger numberOfMatches = 0;
    NSError *error = nil;
    NSRegularExpression *regex = [NSRegularExpression regularExpressionWithPattern:subString
                                                                           options:NSRegularExpressionCaseInsensitive error:&error];


    if (!error)
        numberOfMatches = [regex numberOfMatchesInString:string options:0 range:NSMakeRange(0, [string length])];

    return numberOfMatches;
}

注意： 为避免过多循环，您可能需要去除 evaluatedObject 以便不检查重复值。例如，如果 evaluatedObject = @"aaa"，它会查找 3 次 "a"。因此，删除其中的重复值可能提高速度。这里有一个solution。所以代码将在谓词块中：

NSString *evaluatedWithoutRepeat = [evaluatedObject removeDuplicatedCharacters];
for (NSUInteger index = 0; index <= [evaluatedWithoutRepeat length]; index ++)
{
    NSString *subString = [evaluatedWithoutRepeat substringWithRange:NSMakeRange:(index,1)];
    //The rest would be the same.
}

工作测试：

NSArray *testValues = @[@"inputString",
                        @"input",
                        @"string",
                        @"put",
                        @"strinpg",
                        @"Stringpg",
                        @"stringNOTWANTED"];
NSLog(@"AllValues: %@", testValues);

NSLog(@"Test: %@", [testValues filteredArrayUsingPredicate:predicate]);

输出：

> AllValues: (
    inputString,
    input,
    string,
    put,
    strinpg,
    Stringpg,
    stringNOTWANTED
)
> Test: (
    inputString,
    input,
    string,
    put,
    strinpg
)

Answer 4

您 NSPredicate 的方向是正确的。您正在寻找的阶段是 fault tolerant 搜索，它已被 Levenshtein distance 解决。您基本上需要做的是在单个查询中与查询进行 || 组合。

假设您的所有单词都在 NSArray 中。您需要对其调用一个方法 filteredArrayUsingPredicate:，但是构建这样的谓词并不是那么容易。

所以你的要求是：

搜索词可以是大词的一部分
用户可能会拼错单词

第一部分非常简单，您只需将 CONTAINS 放入谓词即可。第二部分应该像 ?tring or s?ring or st?ing... 并且可以使用简单的 for 轻松构建。您可以试验各种数量的 ? 标志，看看哪个符合您的标准。

Answer 5

NSMutableArray *foundWords = [NSMutableArray new];
for (NSString *knownWord in vocabulary)
{
    if ([input rangeOfString:knownWord].location != NSNotFound)
    {
        [foundWords addObject:knownWord];
    }
}

你可以通过准备词汇来做到这一点。您应该只包含以输入词包含的字母开头的词。

如何从 ios 中的输入字符串中搜索所有单词？

How to search all words from input string in ios?

recursion

search

filter

nspredicate

ios