Способы и системы сегментации текста

Изобретение относится к способам и системам для сегментации текста. Изобретение позволяет повысить скорость сегментации текста. Обращаются к строке символов (204), определяют длинную лексему (206), фиксируют смежные символы в длинной лексеме (208), определяют лексемы из строки символов, удерживая вместе зафиксированные смежные символы, и определяют множество сочетаний лексем (210), причем число сочетаний лексем сокращают при помощи зафиксированных смежных символов. 2 н. и 20 з.п. ф-лы, 3 ил.

 

ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ

Настоящее изобретение относится к сегментации текстов в целом и к сегментации строк символов в частности.

УРОВЕНЬ ТЕХНИКИ

Существуют способы и системы обработки текста, которые пытаются интерпретировать данные, представляющие собой текст. Более затруднительна обработка текста, когда получена строка символов, не имеющая разрывов, которые указывают на слова и другие лексемы. При обработке такой строки символов один из первых шагов заключается в сегментации строки на лексемы с целью интерпретации строки. Такими лексемами могут быть слова, акронимы, аббревиатуры, собственные имена, географические названия, условные сокращенные названия ценных бумаг и другие лексемы.

В зависимости от длины строки символов число возможных сочетаний лексем может быть большим. Однако, как правило, процесс сегментации необходимо выполнить с высокой скоростью.

Примером короткой строки текста служит доменное имя. Доменное имя определяет местонахождение организации или другого объекта в Интернете. Например, доменное имя <www.google.com> определяет местонахождение компании Google Inc во Всемирной паутине по определенному IP-адресу. Желательно уметь разбивать доменное имя на лексемы, так чтобы можно было интерпретировать эти лексемы.

КРАТКАЯ СУЩНОСТЬ ИЗОБРЕТЕНИЯ

Варианты осуществления настоящего изобретения включают в себя способы и системы сегментации текста. Варианты осуществления позволяют находить лексемы в строках текста. Один аспект осуществления настоящего изобретения заключается в том, что обращаются к строке символов, определяют какие-либо длинные лексемы, фиксируют смежные символы в длинной лексеме, определяют лексемы из строки символов, удерживая вместе зафиксированные смежные символы, и определяют для строки символов множество сочетаний лексем, причем число сочетаний лексем сокращают при помощи зафиксированных смежных символов. Можно определить множество длинных лексем, и смежные символы фиксируют в каждой длинной лексеме. У настоящего изобретения имеются дополнительные аспекты, относящиеся к компьютерным системам и машиночитаемым носителям, которые обладают характеристиками, связанными с вышеуказанными аспектами.

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

Эти и другие характеристики, аспекты и преимущества настоящего изобретения будут более понятны после прочтения нижеприведенного подробного описания со ссылкой на прилагаемые чертежи, которые включают в себя:

ФИГ.1 иллюстрирует блок-схему системы в соответствии с одним вариантом осуществления настоящего изобретения;

ФИГ.2 иллюстрирует схему последовательности операций способа в соответствии с одним вариантом осуществления настоящего изобретения;

ФИГ.3 иллюстрирует собой подпрограмму способа, изображенного на ФИГ.2.

ПОДРОБНОЕ ОПИСАНИЕ

Настоящее изобретение включает в себя способы и системы для сегментации текста, в том числе способы и системы для выявления лексем в строке символов. Ниже приводятся подробные описания примеров вариантов осуществления изобретения, поясняемые в тексте и на прилагаемых чертежах. Специалистам в данной области техники должно быть ясно, что возможны многие другие варианты осуществления, соответствующие настоящему изобретению. Для обозначения одинаковых или подобных элементов на чертежах и в дальнейшем описании используются одинаковые номера.

В соответствии с настоящим изобретением могут быть созданы различные системы. На ФИГ.1 приведена схема, поясняющая пример системы, в рамках которой могут быть реализованы варианты осуществления настоящего изобретения. Настоящее изобретение может также быть реализовано и воплощено в виде других систем.

Система 100, изображенная на ФИГ.1, включает в себя множество клиентских устройств 102a-n, серверное устройство 104 и сеть 106. Изображенная сеть 106 включает в себя Интернет. В других вариантах осуществления могут использоваться другие сети, например интрасеть. Кроме того, способы по настоящему изобретению могут быть осуществлены на одном компьютере. Каждое из изображенных клиентских устройств 102a-n включает в себя машиночитаемый носитель, такой как оперативная память (RAM) в приведенном варианте осуществления, соединенный с процессором.

Процессор 110 выполняет набор выполняемых компьютером команд, хранящихся в памяти 108. Такие процессоры могут включать в себя микропроцессор, специализированные интегральные схемы и конечные автоматы. Такие процессоры включают в себя носители или могут быть связаны с носителями, например с машиночитаемыми носителями, где хранятся команды, которые при выполнении их процессором обеспечивают выполнение процессором описанных здесь этапов.

Варианты осуществления машиночитаемых носителей включают в себя, в частности, электронное, оптическое, магнитное или иное запоминающее или передающее устройство, способное снабдить процессор, например процессор, связанный с сенсорным устройством ввода, машиночитаемыми командами. Другие примеры подходящих носителей включают в себя, в частности, гибкий магнитный диск, компакт-диск, магнитный диск, интегральную схему памяти, ПЗУ, оперативную память, специализированную интегральную схему, сконфигурированный процессор, все оптические носители, все носители на магнитной ленте и другие магнитные носители или любой другой носитель, с которого процессор компьютера может считывать команды. Кроме того, передачу или доставку команд компьютеру могут осуществлять различные иные виды машиночитаемых носителей, в том числе маршрутизатор, частная или общедоступная сеть или иное передающее устройство или канал как проводной, так и беспроводной. Команды могут содержать код на любом языке программирования, в том числе, например, на языке C, C++,C#, Visual Basic, Java и JavaScript.

Клиентские устройства 102a-n могут также включать в себя ряд внешних или внутренних устройств, таких как мышь, CD-ROM, клавиатура, дисплей или другие устройства ввода-вывода. В качестве примеров клиентских устройств 102a-n можно привести персональные компьютеры, цифровые помощники, карманные персональные компьютеры, мобильные телефоны, смартфоны, пейджеры, цифровые планшеты, ноутбуки, процессорные устройства и аналогичные типы систем и устройств. В целом, клиентское устройство 102a-n может представлять собой процессорную платформу любого типа, которая соединена с сетью 106 и которая взаимодействует с одной или несколькими прикладными программами. Изображенные клиентские устройства включают в себя персональные компьютеры, выполняющие прикладную программу, представляющую собой браузер, такой как Internet Explorer^TM, версия 6.0, от компании Microsoft Corporation, Netscape Navigator^TM, версия 7.1, от компании Netscape Communications Corporation и Safari^TM, версия 1.0, от компании Apple Computer.

При помощи клиентских устройств 102a-n пользователи 112a-n могут связываться по сети 106 друг с другом и с другими системами и устройствами, подключенными к сети 106. Как показано на ФИГ.1, к сети 106 также подключено серверное устройство 104.

Изображенное серверное устройство 104 включает в себя сервер, выполняющий прикладную программу механизма сегментации, находящуюся в памяти 118. Аналогично клиентским устройствам 102a-n изображенное серверное устройство 104 включает в себя процессор 116, соединенный с машиночитаемой памятью 118. Серверное устройство 104, изображенное в виде отдельной компьютерной системы, может быть осуществлено в виде сети компьютерных процессоров. Примерами серверного устройства 104 служат серверы, универсальные компьютеры, сетевые компьютеры, процессорное устройство и системы и устройства аналогичного типа. Клиентские процессоры 110 и серверный процессор 116 могут представлять собой любой процессор из множества известных компьютерных процессоров, таких как процессоры от компаний Intel Corporation, Санта-Клара, штат Калифорния и Motorola Corporation, Шаумбург, штат Иллинойс. Серверное устройство 104 может также быть соединено с базой данных 126.

Серверное устройство 104, или связанное с ним устройство, может обращаться к сети 106 для получения строки символов от других устройств или систем, подключенных к сети 106. Символы могут включать в себя, например, знаки или символы, используемые в системе записи, в том числе данные, представляющие символ ASCII, ANSI и расширенного двоично-десятичного кода обмена информацией (EBCDIC) или любого другого подходящего набора символов.

В одном варианте осуществления механизм сегментации 120 сегментирует строку символов на потенциальные сочетания лексем. Лексема может включать в себя слово, имя собственное, географическое название, аббревиатуру, акроним, условное сокращенное название ценной бумаги или другие лексемы. Механизм 120 сегментации содержит процессор 122 длинных лексем и процессор 124 лексем. В изображенном варианте осуществления каждый процессор содержит машинный код, постоянно находящийся в памяти 118. Процессор 122 длинных лексем подбирает известные длинные лексемы в строке символов и фиксирует смежные символы, содержащиеся в длинной лексеме. Процессор 124 лексем использует зафиксированные символы для определения списка возможных сочетаний лексем, получаемых из строки символов. В одном варианте осуществления процессор 124 лексем определяет вероятность для каждого сочетания в списке. Другие функции и характеристики процессора 122 длинных лексем и процессора 124 лексем описаны ниже.

Серверное устройство 104 также обеспечивает доступ к другим элементам хранения данных, например к элементу хранения лексем, в приведенном примере - к базе данных 120 лексем. База данных лексем может использоваться для хранения лексем. Элементы хранения данных могут включать в себя любой способ хранения данных или их сочетание, включая в себя, в частности, массивы, хэш-таблицы, перечни и пары. Серверное устройство 104 может иметь доступ и к другим устройствам хранения данных аналогичного типа.

Следует отметить, что настоящее изобретение может содержать системы, имеющие иную архитектуру по сравнению с изображенной на ФИГ.1. Например, в некоторых системах, осуществленных по настоящему изобретению, процессор 122 длинных лексем может не быть частью механизма 120 сегментации или может располагаться не на том же серверном устройстве. Система 100, приведенная на ФИГ.1, служит исключительно для иллюстрации и используется для объяснения варианта осуществления способа, изображенного на ФИГ.2-3.

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

В одном варианте осуществления число символов в длинной лексеме превышает семь. Зафиксированные смежные символы могут представлять собой набор символов, начиная со второго символа в длинной лексеме и заканчивая предпоследним символом в длинной лексеме.

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

ФИГ.2 иллюстрирует пример способа согласно варианту осуществления настоящего изобретения. Этот пример способа приведен в качестве иллюстрации, поскольку существует множество путей реализации способов согласно настоящему изобретению. Ниже в качестве примера описан способ 200, который реализует система 100, изображенная на ФИГ.1, и объяснение примера способа, изображенного на ФИГ.2, приводится со ссылкой на различные элементы системы 100.

Приведенный способ 200 реализует способ выявления лексем из строки символов. Каждый блок на ФИГ.2 представляет один или несколько этапов, осуществляемых в соответствии с примером способа 200. Как показано на ФИГ.2, пример способа 200 начинается в блоке 202. За блоком 202 следует блок 203, в котором механизм сегментации получает строку символов. Строка символов может быть получена, например, из устройства, подключенного к сети, или из другого устройства.

За блоком 204 следует блок 206, в котором процессор 122 длинных лексем определяет длинные лексемы. Число символов в длинной лексеме может быть, например, больше или равно восьми. В качестве длинной лексемы может быть выбрано любое число символов. Длинные лексемы могут быть получены из базы данных 126 лексем, из устройства, подключенного к сети 106, или из другого устройства. Процессор 122 длинных лексем пытается найти соответствие между длинными лексемами и соседними символами в строке символов. В одном варианте осуществления процессор 122 длинных лексем может начать с первого символа строки и пытаться найти соответствие между следующими семью соседними символами и известной длинной лексемой. Если для первых восьми символов не найдено ни одной лексемы, то процессор 122 длинных лексем может перейти далее по строке, начав со второго символа и следующих семи соседних символов, и так далее, пока не будет достигнут конец строки. Для каждой строки символов может быть найдено множество длинных лексем.

Например, для строки символов "transformationofprobability" процессор 122 длинных лексем может начать с символа "t" и семи соседних символов "ransfor". Процессор 122 длинных лексем может определить, что символы "transfor" потенциально могут соответствовать некоторым длинным лексемам, таким как "transform" и "transformation". Процессор 122 длинных лексем продолжает считывать символы и пытаться найти соответствие между символам. Когда, например, процессор 122 длинных лексем получает символ "m", процессор находит соответствие символов с длинной лексемой "transform". Однако после получения следующего символа "a" процессор 122 длинных лексем продолжает получать символы, пытаясь определить, можно ли эти символы поставить в соответствие с более длинной лексемой, например с лексемой "transformation". В данном примере символы могут быть поставлены в соответствие с лексемой "transformation". После получения следующего символа "o" процессор 122 длинных лексем не может поставить символы "transformationo" в соответствие ни с какой длинной лексемой, так что он может определить, что первые четырнадцать символов следует поставить в соответствие с лексемой "transformation", и продолжить обработку. Процессор 122 длинных лексем не может найти соответствие двух последующих наборов из восьми символов, начинающихся с "o" и "f", с какой-либо лексемой. Процессор 122 длинных лексем может затем определить, что следующая группа символов "probabil" может быть поставлена в соответствие с длинной лексемой, и продолжить получать символы. Затем процессор 122 длинных лексем может поставить длинную лексему "probability" в соответствие с остальными символами в строке.

За блоком 206 следует блок 208, в котором процессор длинных лексем фиксирует выявленные длинные лексемы. Посредством фиксации символов процессор длинных лексем указывает, что эти символы должны использоваться совместно в одной лексеме. Благодаря фиксации символов в длинных лексемах строки текста сокращается число возможных сочетаний лексем в строке текста, и тем самым повышается скорость обработки. Процессор 122 длинных лексем фиксирует смежные символы в середине выявленной длинной лексемы. В одном варианте осуществления процессор 122 длинных лексем фиксирует все символы в выявленной длинной лексеме за исключением одного символа на каждом конце лексемы. Например, в приведенном выше примере процессор длинных лексем может зафиксировать символы "ransformatio" выявленной длинной лексемы "transformation" и может зафиксировать символы "robabilit" выявленной длинной лексемы "probability". В альтернативном варианте процессор 122 длинных лексем может оставлять нефиксированными по два или три символа на каждом конце выявленной длинной лексемы. В описываемом варианте осуществления символы на концах лексемы оставляют нефиксированными для того, чтобы не допустить фиксации символов, которые выглядят, как префикс или суффикс длинной лексемы, но на самом деле являются частью другой лексемы.

За блоком 208 следует блок 210, в котором процессор 124 лексем определяет потенциальные сочетания лексем. Процессор 122 длинных лексем передает процессору 124 лексем все зафиксированные символы, определенные в блоке 208. Процессор 124 лексем сопоставляет строку символов со множеством лексем с учетом всех зафиксированных символов. Выполнение подпрограммы 210 продолжается до тех пор, пока не будут выявлены все потенциальные сочетания лексем и не будет создан список всех потенциальных сочетаний лексем. В одном варианте осуществления процессор 124 лексем может "вырезать" один или несколько соседних символов, которые не могут соответствовать лексеме для конкретного сочетания лексем. После вырезания одного или нескольких соседних символов вырезанные символы не учитываются при подборе лексемы для конкретного сочетания лексем. Например, для строки символов "fortheheart", из которой разрешается вырезать символы (обозначаемые "x"), список потенциальных сочетаний лексем может включать в себя: "for the heart", "fort heart", "fort he art" и "for x heart".

На ФИГ.3 приведен пример подпрограммы 210, реализующей способ 200, изображенный на ФИГ.2. Подпрограмма 210 определяет потенциальные сочетания лексем для строки символов. Ниже приведен пример этой подпрограммы.

Подпрограмма начинается в блоке 300. В блоке 300 процессор 124 лексем получает группу соседних символов или обращается к группе соседних символов. В одном варианте осуществления получают, по меньшей мере, два символа. В альтернативном варианте может быть получен один символ. В одном варианте осуществления процессор 124 лексем начинает с одного конца строки символов и проходит через множество потенциальных путей лексем до тех пор, пока не будут определены все многочисленные возможности сочетаний символов для данной строки.

За блоком 300 следует блок 303, в котором процессор 122 лексем определяет, соответствуют ли полученные символы каким-либо путям лексем. В одном варианте осуществления лексемы сохраняют в виде древовидной структуры, где, например, каждый символ находится в вершине дерева и каждая ступень вниз по дереву добавляет символ лексемы. Например, для лексемы "apple", в вершине дерева находится "a", на следующей ступени вниз находится "p", на следующей ступени вниз находится "p", на следующей ступени вниз находится "l" и на следующей ступени вниз находится "e". На каждой ступени дерево может ответвляться на другие пути, которые образуют различные другие лексемы. Например, для лексемы "applied" путь лексемы для символов "appl" тот же самый, что и для лексемы "apple", а затем она ответвляется к "i", затем к "e" и затем к "d", чтобы получить "applied", вместо того, чтобы ответвляться к "e", чтобы получить "apple". Одним из примеров такой древовидной структуры служит тернарное дерево. Если, например, в блоке 300 получены символы "tra", то в блоке 302 процессор 122 лексем может определить, что существует, по меньшей мере, один путь, который начинается с символов "tra". В одном варианте осуществления, если получено только два символа, процессор 124 лексем пытается сопоставить эти два символа с ограниченным числом двухбуквенных лексем и не пытается сопоставить два символа с путем лексемы.

Если символы, обработанные в блоке 302, не соответствуют никаким путям лексем, то процессор лексем возвращается в блок 300 и получает новый набор соседних символов. Например, если получены символы "12d" и эти символы не соответствуют никакому пути лексемы, то есть никакая лексема не начинается с символов "12d", то процессор лексем возвращается в блок 300 и получает новую группу соседних символов. Например, это может быть группа, начинающаяся с символов "2d". Подпрограмма 210 может представлять собой рекурсивный цикл, так что следующий набор соседних символов может начинаться с любого номера места в строке, например со следующего символа после конца найденной лексемы. Можно проследить все потенциальные пути лексем, которые могут быть образованы из символов строки. Число сочетаний лексем сокращают посредством фиксации символов в длинных лексемах.

Если в блоке 302 определено, что путь лексемы существует, то в блоке 304 процессор 124 лексем определяет, соответствует ли эта группа символов какой-нибудь лексеме. Например, если получены символы "tra", то процессор лексем определяет, существует ли какая-нибудь лексема для символов "tra".

Если в блоке 304 определено, что лексемы не существует, то в блоке 306 процессор 124 лексем получает следующий соседний символ, образуя модифицированную группу соседних символов. Затем в блоке 302 процессор 124 лексем может определить, соответствует ли модифицированная группа каким-либо путям лексем. Для примера "transformationofprobability" после того как получены символы "tra", следующим соседним символом является "n", и процессор 124 лексем определяет, соответствует ли "tran" пути или путям лексем. В данном примере действительно имеет место соответствие с несколькими путями, и цикл продолжается до тех пор, пока не будет определена какая-нибудь лексема. Например, цикл продолжается до тех пор, пока не будут приняты все символы "transform", потому что, например, "transform" является лексемой.

После того как в блоке 304 определена лексема, процессор 124 лексем далее определяет, имеются ли зафиксированные символы. Если никакие из полученных символов не являются зафиксированными, то процессор 124 лексем помечает потенциальный разрыв между лексемами, получает следующий соседний символ и переходит к блоку 302.

Если процессор 124 лексем определяет в блоке 308, что некоторые символы были зафиксированы, то процессор 124 лексем определяет в блоке 310, все ли зафиксированные смежные символы были получены. Когда в вышеприведенном примере для "transformationofprobability" получены символы "transformation", процессор 124 лексем определяет, что получены все соседние зафиксированные символы. Если же, например, получены только символы "trans", процессор 124 лексем определяет, что получены не все соседние зафиксированные символы. Если не допускать образования лексем (или разрывов между лексемами) внутри соседних зафиксированных символов, можно значительно сократить число сочетаний лексем для строки символов.

Если получены все соседние зафиксированные символы, процессор 124 лексем сохраняет лексему в блоке 312. Затем процессор лексем получает в блоке 306 следующий соседний символ и продолжает выполнять рекурсивный цикл в блоке 302.

Если получены не все соседние зафиксированные символы, процессор 124 лексем получает в блоке 306 следующий соседний символ и продолжает выполнять рекурсивный цикл в блоке 302. В одном варианте осуществления сначала получают следующий соседний символ, а затем определяют, все ли соседние зафиксированные символы получены. Например, если получены символы "transform", процессор лексем может пометить потенциальный разрыв между лексемами. Однако, когда получен следующий соседний символ "a" и определено, что этот символ был зафиксирован, потенциальный разрыв между лексемами после "transform" может игнорироваться. После получения остальных символов в "transformation", "transformation" сохраняется в качестве лексемы. В альтернативном варианте вместо сохранения лексемы можно сохранить потенциальный разрыв между лексемами после "transformation".

После сохранения известной полной лексемы получают следующий соседний символ в блоке 306, и процессор 124 лексем продолжает выполнение подпрограммы 210 в блоке 302. Если соответствие с лексемами не найдено, процессор 124 лексем получает новую группу соседних символов. Например, в одном варианте осуществления новая группа соседних символов может начинаться с символа, следующего за последним символом наименьшей, ранее выявленной лексемы. Таким образом, проверяются все потенциальные пути лексем, выявляются все потенциальные сочетания лексем для данной строки, и составляется список всех потенциальных сочетаний лексем.

Если вновь обратиться к ФИГ.2, то за блоком 210 следует блок 212, в котором процессор 124 лексем определяет правдоподобие или вероятность для каждого сочетания в списке. В одном варианте осуществления вероятность каждого сочетания основана на частотности лексем в сочетании. Частотность лексем может быть определена заранее из анализа Всемирной паутины. Частотности лексем могут быть перемножены и затем смещены на основании числа слов в сочетании. Вырезанным символам можно присвоить низкое правдоподобие.

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

Настоящее изобретение можно использовать в различных приложениях, где требуется сегментация текста, например доменного имени. Например, настоящее изобретение может использоваться в Интернете совместно с рекламным продуктом на основе доменных имен. Если пользователь вводит доменное имя несуществующего сайта в Интернете, можно воспользоваться механизмом сегментации для сегментации введенного доменного имени, так что пользователю может быть представлен интернет-сайт или рекламная информация, соответствующая введенному тексту. Аналогично, настоящее изобретение можно использовать для сегментации введенного доменного имени, так чтобы пользователю была отображена рекламная информация, соответствующая доменному имени. Настоящее изобретение можно также использовать в том случае, когда пользователь желает купить доменное имя, но это доменное имя занято. Механизм сегментации может сегментировать введенное доменное имя, и эта информация может быть использована для того, чтобы предложить другие подобные доменные имена, которые не заняты.

Хотя вышеприведенное описание содержит множество конкретных сведений, эти конкретные сведения должны рассматриваться не в качестве ограничений объема изобретения, но лишь в качестве иллюстрации раскрытых вариантов осуществления. Специалисту в данной области техники будет ясно, что возможно множество других возможных модификаций, которые соответствуют духу и объему изобретения, описанного выше и определенного нижеприведенной формулой.

1. Способ сегментации строки символов, содержащий этапы, на которых обращаются к строке символов, находят в указанной строке символов по меньшей мере одну длинную лексему, число символов в которой превышает заданное, фиксируют часть смежных символов в длинной лексеме; определяют лексемы из строки символов, не допуская разрывов между лексемами внутри смежных зафиксированных символов, и определяют множество сочетаний лексем для строки символов, причем число сочетаний лексем сокращают при помощи зафиксированных смежных символов.

2. Способ по п.1, в котором находят множество длинных лексем, в каждой длинной лексеме фиксируют часть смежных символов, и определение лексем включает в себя недопущение разрывов между лексемами внутри зафиксированных смежных символов для каждой длинной лексемы.

3. Способ по п.1, в котором определение лексем содержит этапы, на которых (a) обращаются к соседним символам до тех пор, пока не найдено соответствие между первой группой соседних символов и первой лексемой; и (b) сохраняют первую лексему, если определено, что первая лексема не содержит ни одного зафиксированного символа, или если определено, что первая лексема содержит все зафиксированные смежные символы.

4. Способ по п.3, в котором определение лексем дополнительно содержит этапы, на которых (c) обращаются к следующему соседнему символу для получения модифицированной первой группы соседних символов; (d) определяют, соответствует ли модифицированная первая группа символов лексеме; (e) если модифицированная первая группа символов соответствует второй лексеме, то сохраняют вторую лексему, если определено, что модифицированная группа символов не содержит ни одного зафиксированного символа, или если определено, что модифицированная первая группа содержит все зафиксированные соседние символы для длинной лексемы; и (f) если модифицированная первая группа не соответствует никакой лексеме, то получают вторую группу соседних символов.

5. Способ по п.4, в котором этапы с (а) по (f) повторяют до тех пор, пока не будет определено множество сочетаний лексем.

6. Способ по п.4, в котором вторая группа соседних символов начинается с символа, следующего за последним символом первой сохраненной лексемы.

7. Способ по п.1, дополнительно содержащий этап определения правдоподобия для каждого сочетания лексем.

8. Способ по п.7, дополнительно содержащий этап получения сочетания лексем с наибольшим правдоподобием.

9. Способ по п.7, дополнительно содержащий этап предоставления множества сочетаний лексем с наибольшим правдоподобием.

10. Способ по п.7, дополнительно содержащий этап предоставления пользователю сочетаний лексем, имеющих относительно высокое правдоподобие и позволяющих пользователю выбрать требуемое сочетание лексем.

11. Способ по п.1, в котором зафиксированные смежные символы являются набором смежных символов, начиная со второго символа в длинной лексеме и заканчивая предпоследним символом в длинной лексеме.

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

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

14. Машиночитаемый носитель по п.12, в котором определение лексем содержит

(a) программный код для обращения к соседним символам до тех пор, пока не будет найдено соответствие между первой группой соседних символов и первой лексемой; и

(b) программный код для сохранения первой лексемы, если определено, что первая лексема не содержит ни одного зафиксированного символа, или если определено, что первая лексема содержит все зафиксированные смежные символы.

15. Машиночитаемый носитель по п.14, в котором определение лексем дополнительно содержит (c) программный код для обращения к следующему соседнему символу для получения модифицированной первой группы соседних символов; (d) программный код для определения, соответствует ли модифицированная первая группа лексеме; (e) программный код для сохранения второй лексемы, если модифицированная первая группа соответствует второй лексеме и если определено, что модифицированная первая группа не содержит ни одного зафиксированного символа, или если определено, что модифицированная первая группа содержит все зафиксированные смежные символы для длинной лексемы; и (f) программный код для получения второй группы соседних символов, если модифицированная группа не соответствует ни одной лексеме.

16. Машиночитаемый носитель по п.15, в котором этапы с (а) по (f) повторяются до тех пор, пока не будет определено множество сочетаний лексем.

17. Машиночитаемый носитель по п.15, в котором вторая группа соседних символов начинается с символа, следующего за последним символом первой сохраненной лексемы.

18. Машиночитаемый носитель по п.12, дополнительно содержащий программный код для определения правдоподобия каждого сочетания.

19. Машиночитаемый носитель по п.18, дополнительно содержащий программный код для предоставления сочетания с наибольшим правдоподобием.

20. Машиночитаемый носитель по п.18, дополнительно содержащий программный код для предоставления множества сочетаний лексем с наибольшим правдоподобием.

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

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