Оптимизация сканирования большого текста и сопоставления со списком слов или фраз

Question

Я работаю над приложением, которое берет статью (простую страницу HTML) и список терминов словаря (каждый может быть словом, фразой или даже предложением) и создает ссылку для каждого терминанаходит.Проблема в том, что для больших текстов с большим количеством терминов это занимает много времени.В настоящее время мы имеем дело с этим, сначала отображая немаркированный текст, обрабатывая ссылки в фоновом режиме и, наконец, перезагружая веб-представление по окончании обработки.Тем не менее, это может занять некоторое время, и некоторые наши пользователи не довольны этим.

В настоящее время приложение использует простой цикл в терминах, заменяя HTML.В основном:

for (int i=0; i<terms.count; i++){
    NSString *term = [terms objectAtIndex:i];
    NSString *replaceString = [NSString stringWithFormat:@"<a href="myUrl:\\%d>%@</a>", i, term];
    htmlString = [htmlString stringByReplacingOccurrencesOfString:term 
                                                       withString:replaceString 
                                                          options:NSCaseInsensitiveSearch 
                                                            range:NSMakeRange(0, [htmlString length] )];
}

Тем не менее, мы имеем дело с несколькими языками, поэтому существует не одна замена на термин, а двадцать!Это потому, что мы должны иметь дело с пунктуацией в начале (вверх ногами вопросительные знаки на испанском языке) и в конце каждого термина.Мы должны заменить "term", "term." и "term?" соответствующей гиперссылкой.

Есть ли более эффективный метод, который я мог бы использовать для разметки этого HTML-кода?

Iнеобходимо сохранить индекс исходного термина, чтобы его можно было найти позже, когда пользователь щелкнет ссылку.

Answer 1

Вы можете обработать текст следующим образом:

1. Вместо циклического перебора словаря, разделите текст на слова и найдите каждое слово в словаре.

2. Создайте индекс, хэш-таблицу или словарь, чтобы сделать поиск более эффективным.

3. Не использовать stringByReplacingOccurrencesOfString.Каждый раз, когда он вызывается, он копирует весь текст и не освобождает память до тех пор, пока не будет истощен автопул.(Интересно, что у вас еще не было проблем с памятью.) Вместо этого используйте экземпляр NSMutableString, где вы добавляете каждое слово (и символы между ними), как оно было в исходном тексте или оформлено как ссылка.

Answer 2

То, что вы сейчас делаете, это:

for each vocabulary word 'term'
    search the HTML text for instances of term
        replace each instance of term with an appropriate hyperlink

Если у вас большой текст, то каждый поиск занимает намного больше времени. Кроме того, каждый раз, когда вы делаете замену, вы должны создать новую строку, содержащую копию текста, на котором будет производиться замена, поскольку stringByReplacingOccurrencesOfString:withString:options:range: возвращает новую строку, а не изменяет существующую строку. Умножьте это на N замен.

Лучшим вариантом было бы сделать один проход через строку, выполнив поиск по всем терминам одновременно, и создав результирующую выходную строку в изменяемой строке, чтобы избежать Shlemiel, подобного Painter, времени выполнения .

Например, вы можете использовать регулярные выражения примерно так:

// Create a regular expression that is an alternation of all of the vocabulary
// words.  You only need to create this once at startup.
NSMutableString *pattern = [[[NSMutableString alloc] init] autorelease];
[pattern appendString:@"\\b("];

BOOL isFirstTerm = YES;
for (NSString *term in vocabularyList)
{
    if (!isFirstTerm)
    {
        [pattern appendString:@"|"];
        isFirstTerm = NO;
    }
    [pattern appendString:term];
}
[pattern appendString:@")\\b"];

// Create regular expression object
NSError *error = NULL;
NSRegularExpression *regex = [NSRegularExpression regularExpressionWithPattern:pattern options:NSRegularExpressionCaseInsensitive error:&error];

// Replace vocabulary matches with a hyperlink
NSMutableString *htmlCopy = [[htmlString mutableCopy] autorelease];
[regex replaceMatchesInString:htmlCopy
                      options:0
                        range:NSMakeRange(0, [htmlString length])
                 withTemplate:@"<a href=\"vocab.html?word=\\1\">\\1</a>"];
// Now use htmlCopy

Answer 3

Существует два подхода.

1. Хеш-карты - если максимальная длина ваших фраз ограничена, например, двумя, вы можете перебирать все слова и биграммы (2 слова) иотметьте их в HashMap - сложность прямолинейна, так как Hash - это идеальное постоянное время

2. Теория автоматов Вы можете комбинировать простые автоматы, которые обрабатывают строки в один и вычисляют быстрее (т.е. динамическое программирование).Например, у нас есть «John Smith» | «John Stuard», и мы получаем John S (mith | tuard), это так называемая оптимизация префикса (http://code.google.com/p/graph-expression/wiki/RegexpOptimization)

. Здесь можно найти более сложный алгоритм * 1012.*http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm

Мне больше нравится этот подход, потому что нет ограничения длины фразы, и он позволяет комбинировать сложные регулярные выражения.

---

Answer 4

Поскольку функция замены строк, которую вы вызываете, имеет порядок N (она сканирует заменяющие n слов), и вы делаете это для m словарных терминов, у вас есть алгоритм n ^ 2.

Если бы вы могли сделать это за один проход, это было бы оптимально (порядок n - n слов в html).Идея сначала представить незаменимый текст все еще хороша, если только она не будет заметна даже для больших документов.

Как насчет хэширования словарных слов, отсканируйте слово html с помощью (пропуская разметку html), и еслитекущее отсканированное слово находится в наборе хэшей, добавьте его в целевой буфер вместо отсканированного слова.Это позволяет хранить в памяти не более 2 х содержимого html + 1 хэш словарных слов.