Method of searching character string, character string searching device, and recording medium

Patent metadata

Field	Value
Publication number	US-9645828-B2
Application number	US-201414287634-A
Country	US
Kind code	B2
Filing date	May 27, 2014
Priority date	May 30, 2013
Publication date	May 9, 2017
Grant date	May 9, 2017

Abstract

A method includes comparing, in units of a first bit length, a first bit sequence of the first bit length included in a search character bit sequence to a second bit sequence of a second bit length included in a target character bit sequence; when a third bit sequence of the first bit length following the first bit sequence in the search character bit sequence matches a fourth bit sequence of the first bit length following a location matching the first bit sequence in the second bit sequence, creating a fifth bit sequence of the second bit length starting from a location matching the first bit sequence in the target character bit sequence; comparing, in units of the first bit length, the fifth bit sequence to a sixth bit sequence of the second bit length starting from the first bit sequence in the search character bit sequence; and determining.

First claim

What is claimed is:

1. A method of searching character string, the method comprising:
first comparing, in units of a first bit length, a first bit sequence of the first bit length included in a search character bit sequence corresponding to a search character string to a second bit sequence of a second bit length included in a target character bit sequence corresponding to a target character string;
when a third bit sequence of the first bit length following the first bit sequence in the search character bit sequence matches a fourth bit sequence of the first bit length following a location matching the first bit sequence in the second bit sequence, creating a fifth bit sequence of the second bit length starting from a location matching the first bit sequence in the target character bit sequence;
second comparing, in units of the first bit length, the fifth bit sequence to a sixth bit sequence of the second bit length starting from the first bit sequence in the search character bit sequence; and
determining, based on a result of the second comparing, whether or not the search character string is included in the target character string.

2. The method according to claim 1 , further comprising:
when the search character string and the target character string are a specific character encoding, in a case in which the third bit sequence and the fourth bit sequence match, comparing a seventh bit sequence of the first bit length following the third bit sequence in the search character bit sequence to an eighth bit sequence of the first bit length following the fourth bit sequence in the target character bit sequence,
wherein the creating is executed when the seventh bit sequence and the eighth bit sequence match.

3. The method according to claim 1 , wherein
the first bit length is 1 byte, and
the second bit length is a bit length expressing a unit of processing of a compare instruction that batch compares bit sequences to each other in units of bytes.

4. The method according to claim 3 , further comprising:
third comparing the third bit sequence to the fourth bit sequence when the search character string and the target character string are multibyte characters, and a location matching the first bit sequence in the second bit sequence is a first byte of a multibyte character.

5. The method according to claim 1 , further comprising:
storing a bit sequence from the first bit sequence and equal in length to the second bit length in a first register; and
storing the second bit sequence in a second register,
wherein the first comparing compares, in units of the first bit length, the bit sequence stored in the first register to the bit sequence stored in the second register.

6. The method according to claim 5 , further comprising:
storing a ninth bit sequence of the second bit length following the second bit sequence in the target character bit sequence in a third register;
in the second register, left-shifting the bit sequence and first masking bits of the shift origin; and
in the third register, right-shifting the bit sequence and second masking bits of the shift origin;
wherein the creating creates the fifth bit sequence by taking a logical OR of a bit sequence stored in the second register after the first masking, and a bit sequence stored in the third register after the second masking.

7. The method according to claim 6 , further comprising:
storing a bit sequence of the second bit length starting from the first bit sequence in the search character bit sequence in a fourth register; and
storing the fifth bit sequence in a fifth register;
wherein the second comparing compares, in units of the first bit length, a bit sequence stored in the fourth register to a bit sequence stored in the fifth register.

8. The method according to claim 5 , further comprising:
when the second bit sequence does not include a bit sequence matching the first bit sequence, storing the ninth bit sequence in the second register as the second bit sequence.

9. A character string searching device comprising:
a memory; and
a processor coupled to the memory and configured to execute a process including:
first comparing, in units of a first bit length, a first bit sequence of the first bit length included in a search character bit sequence corresponding to a search character string to a second bit sequence of a second bit length included in a target character bit sequence corresponding to a target character string,
when a third bit sequence of the first bit length following the first bit sequence in the search character bit sequence matches a fourth bit sequence of the first bit length following a location matching the first bit sequence in the second bit sequence, creating a fifth bit sequence of the second bit length starting from a location matching the first bit sequence in the target character bit sequence,
second comparing, in units of the first bit length, the fifth bit sequence to a sixth bit sequence of the second bit length starting from the first bit sequence in the search character bit sequence, and
determining, based on a result of the second comparing, whether or not the search character string is included in the target character string.

10. The character string searching device according to claim 9 , the process further including:
when the search character string and the target character string are a specific character encoding, in a case in which the third bit sequence and the fourth bit sequence match, comparing a seventh bit sequence of the first bit length following the third bit sequence in the search character bit sequence to an eighth bit sequence of the first bit length following the fourth bit sequence in the target character bit sequence,
wherein the creating is executed when the seventh bit sequence and the eighth bit sequence match.

11. The character string searching device according to claim 9 , wherein
the first bit length is 1 byte, and
the second bit length is a bit length expressing a unit of processing of a compare instruction that batch compares bit sequences to each other in units of bytes.

12. The character string searching device according to claim 11 , the process further including:
third comparing the third bit sequence to the fourth bit sequence when the search character string and the target character string are multibyte characters, and a location matching the first bit sequence in the second bit sequence is a first byte of a multibyte character.

13. The character string searching device according to claim 9 , the process further including:
storing a bit sequence from the first bit sequence and equal in length to the second bit length in a first register, and
storing the second bit sequence in a second register,
wherein the first comparing compares, in units of the first bit length, the bit sequence stored in the first register to the bit sequence stored in the second register.

14. The character string searching device according to claim 13 , the process further including:
storing a ninth bit sequence of the second bit length following the second bit sequence in the target character bit sequence in a third register,
in the second register, left-shifting the bit sequence and first masking bits of the shift origin, and
in the third register, right-shifting the bit sequence and second masking bits of the shift origin,
wherein the creating creates the fifth bit sequence by taking a logical OR of a bit sequence stored in the second register after the first masking, and a bit sequence stored in the third register after the second masking.

15. The character string se

Assignees

• Fujitsu Ltd

Inventors

• Sugiyama Kokichi
• Sano Takayuki
• Itou Naohiro
• Yoshida Mikio
• Kurokawa Toshiyuki
• Yoshinaga Motonori

Classifications

• G06F15/8007

  single instruction multiple data [SIMD] multiprocessors · CPC title

• G06F2207/025

  String search, i.e. pattern matching, e.g. find identical word or best match in a string · CPC title

• G06F17/30985

  Physics · mapped topic

• G06F9/3887 Primary

  controlled by a single instruction for multiple data lanes [SIMD] · CPC title

• G06F16/90344 Primary

  by using string matching techniques · CPC title