iphone - 正则表达式模式和/或 NSRegularExpression 在非常大的文件上搜索有点太慢了，可以优化吗？

Question

在 iOS 框架中，我在这个 3.2 MB 的文件中搜索发音:https://cmusphinx.svn.sourceforge.net/svnroot/cmusphinx/trunk/pocketsphinx/model/lm/en_US/cmu07a.dic

我正在使用 NSRegularExpression 搜索作为 NSArray 给出的任意一组单词。搜索是通过大文件的内容作为 NSString 完成的。我需要匹配出现在换行符和制表符括号内的任何单词，然后抓取整行，例如，如果我的 NSArray 中有单词“monday”，我想匹配字典文件中的这一行:

monday  M AH N D IY

这一行以一个换行符开始，字符串“monday”后跟一个制表符，然后是读音。整行需要由正则表达式匹配以获得其最终输出。我还需要找到下列单词的替代发音:

monday(2)   M AH N D EY

备选发音始终以 (2) 开头，最高可达 (5)。因此，我还搜索了由换行符和制表符括起来的单个数字后跟圆括号的单词的迭代。

我有一个 100% 正常工作的 NSRegularExpression 方法，如下所示:

NSArray *array = [NSArray arrayWithObjects:@"friday",@"monday",@"saturday",@"sunday", @"thursday",@"tuesday",@"wednesday",nil]; // This array could contain any arbitrary words but they will always be in alphabetical order by the time they get here.

// Use this string to build up the pattern.
NSMutableString *mutablePatternString = [[NSMutableString alloc]initWithString:@"^("]; 

int firstRound = 0;
for(NSString *word in array) {
    if(firstRound == 0) { // this is the first round

        firstRound++;
    } else { // After the first iteration we need an OR operator first.
        [mutablePatternString appendString:[NSString stringWithFormat:@"|"]];
     }
    [mutablePatternString appendString:[NSString stringWithFormat:@"(%@(\\(.\\)|))",word]];
}

[mutablePatternString appendString:@")\\t.*$"];

// This results in this regex pattern:

// ^((change(\(.\)|))|(friday(\(.\)|))|(monday(\(.\)|))|(saturday(\(.\)|))|(sunday(\(.\)|))|(thursday(\(.\)|))|(tuesday(\(.\)|))|(wednesday(\(.\)|)))\t.*$

NSRegularExpression * regularExpression = [NSRegularExpression regularExpressionWithPattern:mutablePatternString
                                                                                     options:NSRegularExpressionAnchorsMatchLines
                                                                                       error:nil];
int rangeLocation = 0;
int rangeLength = [string length];
NSMutableArray * matches = [NSMutableArray array];
[regularExpression enumerateMatchesInString:string
                                     options:0
                                       range:NSMakeRange(rangeLocation, rangeLength)
                                  usingBlock:^(NSTextCheckingResult *result, NSMatchingFlags flags, BOOL *stop){
                                      [matches addObject:[string substringWithRange:result.range]];
                                  }];

[mutablePatternString release];

// matches array is returned to the caller.

我的问题是考虑到大文本文件，它在 iPhone 上的速度真的不够快。 8 个单词在 iPhone 4 上需要 1.3 秒，这对于应用程序来说太长了。鉴于以下已知因素:

• 3.2 MB 的文本文件包含按字母顺序列出的匹配词

• 到达此方法时，要查找的任意单词数组始终按字母顺序排列

• 备选发音在单词后面的括号中以 (2) 开头，而不是 (1)

• 如果没有 (2) 就不会有 (3)、(4) 或更多

• 出现一种替代发音的情况很少见，平均每 8 次出现 1 次。更多的替代发音更加罕见。

可以通过改进正则表达式或 Objective-C 的某些方面来优化此方法吗？我假设 NSRegularExpression 已经足够优化，因此不值得尝试使用不同的 Objective-C 库或在 C 中执行它，但如果我在这里错了，请告诉我。否则，非常感谢有关改进性能的任何建议。我希望将其推广到任何发音文件，因此我尽量避免使用提前计算字母范围等解决方案，以进行更多受限搜索。

****编辑****

以下是 2012 年 8 月 16 日之前在 iPhone 4 上给出的所有搜索相关答案的时间:

dasblinkenlight 的创建 NSDictionary 方法 https://stackoverflow.com/a/11958852/119717 : 5.259676 秒

Ωmega 最快的正则表达式 https://stackoverflow.com/a/11957535/119717 : 0.609593 秒

dasblinkenlight 的多重 NSRegularExpression 方法在 https://stackoverflow.com/a/11969602/119717 : 1.255130 秒

我的第一个混合方法 https://stackoverflow.com/a/11970549/119717 : 0.372215 秒

我的第二种混合方法 https://stackoverflow.com/a/11970549/119717 : 0.337549 秒

到目前为止最好的时间是我的第二个版本的答案。我不能最好地标记任何答案，因为所有与搜索相关的答案都说明了我在我的版本中采用的方法，所以它们都非常有帮助，而我的只是基于其他答案。我学到了很多东西，我的方法只用了原来四分之一的时间，所以这非常有帮助，感谢 dasblinkenlight 和 Ωmega 与我讨论。

Answer 1

既然无论如何都要将整个文件放入内存，那么不妨将其表示为易于搜索的结构:

• 创建一个可变的 NSDictionary words，带有 NSString 键和 NSMutableArray 值
• 将文件读入内存
• 逐行检查代表文件的字符串
• 对于每一行 ，通过搜索 '(' 或 '\t' 字符来分隔单词部分
• 获取单词的子字符串(从零到 '(' 或 '\t' 的索引减一)；这是你的 键。
• 检查 words 是否包含您的 key；如果没有，添加新的 NSMutableArray
• 将 line 添加到您在特定 key 处找到/创建的 NSMutableArray
• 完成后，丢弃表示文件的原始字符串。

有了这个结构，您应该能够及时进行搜索，任何正则表达式引擎都无法匹配，因为您用散列查找替换了线性的全文扫描，这是常数时间。

** 编辑:** 我检查了这个解决方案与正则表达式的相对速度，它在模拟器上快了大约 60 倍。这一点也不奇怪，因为基于正则表达式的解决方案的可能性很大。

读取文件:

NSBundle *bdl = [NSBundle bundleWithIdentifier:@"com.poof-poof.TestAnim"];
NSString *path = [NSString stringWithFormat:@"%@/words_pron.dic", [bdl bundlePath]];
data = [NSString stringWithContentsOfFile:path encoding:NSUTF8StringEncoding error:nil];
NSMutableDictionary *tmp = [NSMutableDictionary dictionary];
NSUInteger pos = 0;
NSMutableCharacterSet *terminator = [NSMutableCharacterSet characterSetWithCharactersInString:@"\t("];
while (pos != data.length) {
    NSRange remaining = NSMakeRange(pos, data.length-pos);
    NSRange next = [data
        rangeOfCharacterFromSet:[NSCharacterSet newlineCharacterSet]
        options:NSLiteralSearch
        range:remaining
    ];
    if (next.location != NSNotFound) {
        next.length = next.location - pos;
        next.location = pos;
    } else {
        next = remaining;
    }
    pos += (next.length+1);
    NSString *line = [data substringWithRange:next];
    NSRange keyRange = [line rangeOfCharacterFromSet:terminator];
    keyRange.length = keyRange.location;
    keyRange.location = 0;
    NSString *key = [line substringWithRange:keyRange];
    NSMutableArray *array = [tmp objectForKey:key];
    if (!array) {
        array = [NSMutableArray array];
        [tmp setObject:array forKey:key];
    }
    [array addObject:line];
}
dict = tmp; // dict is your NSMutableDictionary ivar

搜索:

NSArray *keys = [NSArray arrayWithObjects:@"sunday", @"monday", @"tuesday", @"wednesday", @"thursday", @"friday", @"saturday", nil];
NSMutableArray *all = [NSMutableArray array];
NSLog(@"Starting...");
for (NSString *key in keys) {
    for (NSString *s in [dict objectForKey:key]) {
        [all addObject:s];
    }
}
NSLog(@"Done! %u", all.count);