JPS5949062A - Information storing system - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Application of the Invention] The present invention relates to a storage system for an information storage device, and particularly to a storage system suitable for document files.

[Prior art]

In recent years, ``Office Automation J'ktJ+'' has increasingly included English and Japanese texts.

These are generally called document processing. Traditionally, the central issue in document processing has been word processing, but there is now a need to store and manage all the large amounts of documents that have been created and collected.

On the other hand, high storage density? Optical disk storage devices are attracting attention as document file devices that store entire documents. However, one of the characteristics of optical discs is that once the information is recorded (note 1.), it cannot be erased or rewritten.Is this a dog's document? This is a drawback when it comes to memorization.

The reason for this is that one of the biggest advantages of multiple document processing is
This is because rewriting such as editing, correction, and proofreading can be done very efficiently, and most documents can be rewritten. In other words, there are very similar documents that have been edited or modified in the document 1'' file device.
In other words, a large number of versions will be stored.

This problem is particularly severe in large documents consisting of many pages that have only been partially changed, resulting in a large number of overlapping entries.

Therefore, in the past, large documents were divided into parts, such as chapters and sections, and each part was recorded as a storage information unit, that is, a file. Ha-I was managing it. In this case, there is a drawback that the complicated management of the versions of each chapter and section f must be done by a person.

In this way, individual memory information units? Conventional storage methods that store files independently of each other have the drawbacks that storage efficiency decreases due to redundant storage, and that managing multiple versions becomes complicated if the files are stored in separate parts. .

Regarding the drawback of decreased storage efficiency due to redundant storage mentioned above, there is a similar problem in the past, in which there is a problem of preserving the entire state quantity at each time in an online system. It is necessary to save the state at each time. Literally all these state quantities? Storing it is impossible because it requires huge storage capacity. Therefore, in the past, all state quantities and master files were stored and saved periodically (for example, once a day), and the state at each time in each period was stored and saved as a master file.
All transactions
n) It is important to memorize the LC, but in the unlikely event that an accident occurs, there is a way to play it back from the master file and transaction.

The key point of this method is to memorize one standard and all of its differences.

The problem with the literature file mentioned above can basically be solved using this idea. The standard file is the first version of a document, and the differences from the second version are determined by the editing program (
(editor) or a word processor.

However, this method has the following problems.

In other words, in general, there are many types of editors and word processors, and in order to play back from the stored sequence of document editing commands, the document file device remembers the single category of the editor or word processor that was used last month. It is necessary to have the same functionality as the editor, word processor, or editor you have memorized.

In the future, document file devices will have independent functions and will be connected to other devices such as word processors, printers, or personal computers via a network. Therefore, the document file device cannot have all the functions of a word processor to which it may be connected.

In other words, the method used in the online system cannot be applied as is.

[Purpose of the invention]

Therefore, the purpose of the present invention is to improve the above-mentioned drawbacks and solve the problem of large amount of documents. To provide a storage tray that can store data with a small storage capacity.

[Summary of the invention]

This purpose? In order to achieve this, in the present invention, regarding the information unit of the warm number to be stored, a specific information unit? The system is characterized by automatically detecting overlapping partials with the specific information unit for other information units, thereby eliminating redundancy and storing only the different parts. According to the method of the present invention, not only the storage capacity can be reduced, but also duplication is automatically detected, so it is possible to use large information units. It is possible to eliminate the need to manage the information by dividing it into small pieces.

[Embodiment of the invention]

Hereinafter, a detailed explanation will be given based on embodiment V of the present invention.

FIG. 1 is a system configuration diagram of an information storage device using sound according to the present invention. This device includes computers 401, 402,
A terminal consisting of a CRT (Cathode I ay Tube) display 403 and a keyboard 404; 3
Types of secondary storage devices 410, 411, 412. And local area, communication system individual package for connection with network.
It consists of 421. In the figure, 461 is a one-word bus of the local area network, and 462 is an internal data bus of this device.

Next, the present invention will be explained in detail with reference to FIGS. 2 to 8. Now, to simplify the explanation, the contents of the two document files are the text (character string) S shown in Figure 2 (1).
1 and S2. The figure shows an example of English text, but Japanese text can also be explained in the same way. The difference is that ``ichiimo'' in English can be expressed in 1 byte, while in Japanese it can be expressed in 2 bytes. Only the essential points are covered. Note that in the figure, the symbol C4L means a line feed code.

Assuming the text of SIk 1st edition and the text of 82 ke 2nd edition, the latter is processed as follows with respect to the former? ``You can get away with saying no.

CI) Exactly quotes except for the first two letters of S.

C2) Next 1α character? delete.

(C3) Quote the next 6 characters.

C4) 9 characters "Xvatcbing△n't-insertion.

(Here, △ means blank?) C5) Continue to quote the 7 characters.

C6) Replace with the next 10 characters t2 characters “TV”.

(Insert 2 characters “TV”r and delete 10 characters) C7) Followed by 12 character quotations.

C8) Next 2 letters 6 letters gold “aZ\dark” and @
A, 1C9) The 7 characters of Hanago are shungetsu.

Therefore, instead of memorizing Szk as is, cl)~
All you have to do is memorize the information in C8). The same information is shown in Figure 2 (2)
It can be expressed as: In the same figure, 1 is the first
The file name of the version document, here Sl, 2 to 4
The new where is inserted.

The character string 10~]3 represents the difference between two characters. Here, the symbols C, D, r.

EOF has the following meanings:

C...Cite D...Delete (1) delete) ■...Insert (In5ert) E OF...End of file (End of p I)
Ic) Also, the numbers following these symbols, e.g. 1
The number 2 following 0C indicates the number of characters. Specifically (C
, 2) represents a two-character quotation.

An example of how to express symbols 10, 12, and 13 in Figure 2 (3)? show. Symbols shown in Figure 2 (2) (Figure 2 (
In 3), the left side 31) is specifically the right side 32 of the same figure (3).
It can be expressed as The code 7832 has 8 pits, the upper 2 bits indicate (C, D, I, EOF), and the lower 6 bits indicate the distinction between (C, D, I, EOF).
A pit indicates its length t in binary. t is θ~63(
2'-1) can be represented by one code. , when t is 64 or more, all the same-recurring sign months are consecutively 311 times, tτ1
It is expressed as 2 pits, 18 bits, etc. For example, when t=689, as shown by symbol 33 in the same figure, it is represented by [l1689]7 with the symbol 34.35 of 1.2 words. The code 36 is a fully equivalent representation of the meanings of the codes 34 and 35', with the first code 34 being the lower one and the second code 35 being the higher one? show.

According to this method, file name 1 is 16 bytes, insertion character strings 2 to 4 are each 1 byte, and a total of 17 bytes.
Also, symbols 10 to 13 indicating differences are each 1 byte, totaling 12
It can be expressed in bytes, and as a result, text s2 having a total length of 51 bytes can be expressed in 16+17+12=45 bytes, reducing the amount required for storage by 6 bytes.

In an actual document, the part that is rewritten is a small part of the entire text, and the effect of reducing the amount of memory is large.

Now, in short, the present invention automatically detects the correspondence between the two texts shown by the K line in FIG. 2 (1), and
9) provides a method for extracting information. Next, this method will be explained.

It is easier to understand the correspondence between texts as shown in Figure 3. The vertical axis is Sl and the horizontal axis is 82. here,·
The mark is 0. X marks delete (G), 0 marks insert (I) x
It represents. These strings of symbols must be continuous from the lower left end point to the upper right end point of the two-dimensional area on the same mesh. On this journey? The l-trowel will be called a pass.

Therefore, detecting the correspondence is equivalent to sequentially searching for this path in this area starting from the lower left end.

The search method will be explained using FIG. Now generally, s t = (a(i))T, t
(1) Let us write S 2 = (b(j) )1゜1(2).

Search is a comparison of a(1) and b(1) (called matching)
K begins. Since a(1) and b(1) are equal, a(1+1
)' and b(i+i), then proceed to matching a(3) and b(3) and fail (a(3) to b(3))
. In Figure 4, we begin the process of searching for the next matching point, which is indicated by a landmark. In the figure, the search area is indicated by a + mark. When searching, proceed in the order of the numbers circled. That is, a(3)b (3)-+ a (3) b(4)→a
(4) b (,3)-a (3) b(5)-to a
(4) b (4)−+ a (,3) b(5)−+
a(3) b((31→-・-(3) then a (G)
b Matching of (3) is successful (a(6)=b(
3)).

At this point, whether or not matching of T characters succeeds continuously from this point onwards, + 8 (6+t), b (3+t) 1. ,
, Matching (4)? Verify by continuing. In the example of Figure 4, a (6+1) b (
3+1) fails and returns to the previous search process to continue the search.

In the end, the 66th matching a (13) b[3] is T
If you succeed against 2, repeat the same process again.

Since the starting point of the search is a (3) b (3) and the ending point (the point where matching was successful) is a(,t3)'b(3], the character substrings a(3) to a(13 -1) is a deletion. General (C starting point chemistry (+1) b(
)・ ), and the end point is a(j2)bN2 ), character substring a(il) to a(i21): Delete (5)
Character substring b(j+)~')(j2t): Insert (
G), and the character substrings that are successfully matched become quotations. However, when il≧12-1, no deletion occurs, j1
When ≧32-1, it is insertion sinking.

This process? What it looks like when continued to the end (r shown in Figure 5. The search area is a right-angled isosceles triangle area indicated by diagonal lines. The number of matching operations in the search is approximately 2.10 times. Here, T-:2.

The parameter ゛P is the matching length, and if it is chosen to be small, the optimum path for the purpose will be found &'L'I
Sometimes it is not possible to find the correct correspondence as a Yo body 3
, FIG. 6 is an example of such a case for T-1.

Although such erroneous correspondence has an effect on the memory of correct information, it makes the storage efficiency smaller than in the optimal case. In situations where the matching portion of the two texts is small (as in Figure 1), this may require more storage than the original dexterity. However, if the value of r is set to a suitably large value, this problem will be reduced in terms of probability. As a systematic measure, the length of the original text and this method (C
By comparison: (Comparing macho (amount) and pregnancy, which one is shorter? There are ways to choose.

How to find the correspondence between the two texts explained above? It's called Hatern matching. Here, a flowchart of the pattern matching algorithm is shown in FIGS. 7(] to 7). This algorithm uses two texts (character code strings)
(1) Input the formula (2) and enter the code string that represents all the differences as shown in Figure 2? Output. Here, the text S1 is the standard, and the difference is one crystal difference of S from S1.

Here, FIGS. 7(1)-(7)(r) will be briefly explained.

In FIG. 7(1), the initial transformation is performed in step 201. Here, i, J are respectively text) pointers to t- to S++82, m, n are text matching +qtt
This is a pointer for storing the end point of the minute and the starting point of the discrepancy. Further, R is a code string representing a difference,
Standard text name (file name) f (Sl)
is initialized to .

Labels 101 to 102 are matching partial texts r
This is a fixing process. If the end of text ('EOF) k is detected in steps 202 and 203, the process jumps to steps 261 and 262 of the end process, respectively. In step 204, it is determined whether or not the two character codes a(i) and b(D) match. If they match, the pointer is advanced in step 205 and the next character code is compared. When Jl, add to the code 7 creation process that expresses all the matching parts (202). In step 202, the ■ symbol represents addition (apl] end). The symbol [Ci7'] is shown in Figure 2. Code 2?
represent. Specifically, for the text name (Ci
te), which means that only t matched.

In FIG. 7(2), the area after label 102 is a search portion where the next matching point is searched for after a character code mismatch is found. If the end of the text is detected during steps 211 and 212, the process jumps to steps 263 and 264 of the end process. Search for the triangular area shown in FIG. 4 in a loop starting at step 213 and returning to 213? Realize. In the processing from step 215 onwards, it is determined whether or not the partial texts match by consecutive T characters. If there is no match, the search continues 7, and if there is a match, the process jumps to label 103.

In FIG. 7(3), a code r is output for the mismatched portion after label 103. In step 231, the symbol [I;
......, b(j+β-1)) Add all.

Since the subsequent parts of the algorithm shown in FIG. 7 can be understood from the above explanation, the pitch name will be explained as P1h.

Now, as can be understood from Fig. 5, the above algorithm (up to i-1, the long part is deleted and inserted t'l-fc, jl), the search area becomes larger and the pattern matching There is a problem in that it takes a long time.

Next, an extended algorithm r for determining the current WWI will be explained.

Principle of expansion algorithm? It is shown in FIG. The principle is to make the unit that performs all matching larger than the character unit. In the case of Figure 8, matching is performed in units of parts separated by spaces (a type of character code). The position is not limited to words, and can be set more generally.

1] is a unit of "line" separated by a line feed code (indicated by the C/几 symbol) - Is this a larger unit? In order to compare in one matching, is there any feature that can be easily compared from the character code string? It is necessary to extract.

In the case of Figure 8, valid features are indicated by numbers inside each quadrilateral.1. This is the length of the name segment, as shown in the following. The length of each segment is (a<1>)"-1, (b(j)l'
, -1, the algorithm shown above can be used exactly as is to search for matching words or lines from two texts.

When a pattern/matching match is encountered in this large unit, in the search process of the algorithm shown in Figure 7 (xo2>-e in the same figure, it is more Then, when you encounter a non-matching part and press J1, search for the next matching word or line while measuring the word or division of 1 loaf/＼?action length, !.

In other words, the extended algorithm is a layered version of the simple pattern matching algorithm described above.

This will be explained in more detail using FIG. 8. First, two texts) S+, 82 is the first two characters ゛■Δ'' (Δ is a blank?
) matches, and the next S″ and “e” do not match 5
Therefore, in the search process, when we first reach the length of the interval (c) divided by blanks (c), 10 and 6 do not match.

Then, as before, we will sequentially expand the triangular purple detection area.

Next, IO and 9 do not match. The lengths of the next 6 and 6 are the same. Therefore, we identify whether or not they really match at the Bunte code level, and distinguish between "enjoy" and "enjoy".
It turns out that they match, and we return to the matching part identification section. Next, a″ and “W” match again and a″ctz:+su・2[
”CEl (7J T'J 'jib iM 'f'L
Proceed in the same way as ICA A.11.

In this way, the extended algorithm can perform pattern matching with a shorter search process than the simple algorithm. In general, if N2M is obtained by deleting or inserting N characters or redeeming M and N characters, the amount of processing in the search process is proportional to N·(N+1)/2 (7). Now, assuming that the average length of a word or line is L characters, the amount of search processing in the extended algorithm is proportional to . Obviously, the larger the length of the unit, the smaller the amount of processing required.

Incidentally, in the case of FIG. 5 (simple algorithm), the search throughput is on the order of 240, and in the case of FIG. 8, it is on the order of 16. However, unlike Equation (8), in Niko, it is not the area of the triangle but the actual number of matchings. I counted.

Next, the case where the storage method of the present invention is applied to the apparatus shown in FIG. 1 will be explained.

Three types of secondary storage devices 41o in the device shown in FIG.

411 and 412t, respectively) Y, disk device, head magnetic disk device, and floppy magnetic disk device. Optical disk devices store frozen permanent information units (files) that will never be changed, or store information units with a large amount of information, such as images (acid data).Fixed head magnetic disk devices store a large number of , storage of the latest version of information units divided into versions, that is, frozen information units that are subject to change; storage of catalogs of information units stored in optical disk devices; There is also a system program that controls the entire device and a processing program that performs word processing, etc.The third secondary storage device, a 70-segment magnetic disk device, is used to store other stand-alone devices. exists for exchanging information with, for example, a word processor.For example, when creating a large number of various types of text with a word processor that is not connected to a network, it is stored and managed by Kanemoto Sono, and the documents are transferred from this device. The file can be read out onto all floppy disks and sent to a word processor, and returned to the present device when the processing power is too high.

This device not only functions as a seven-way station on a local area network, but also has processing functions such as word processing.

Here, we will only explain the basic role of the filing station, which is the center of the invention.
The other functions can be realized using known techniques, so their explanation will be omitted.

A storage request from this device itself or from the entire network is expressed by data having the structure shown in FIG. In the figure, a first record 501 shows the request content, a second record 502 shows the file name at the time of a storage or read request, and a third record shows the attributes of the same file. The fourth and fifth records exist at the time of storage, and are the old file name (the file that became the base file for processing) and the main body of the data to be stored, respectively.

The EOF symbol 506 is placed at the end of the data body 505.

A storage request issued to this device is stored in the spool (SpOOt) on the -J↓ secondary storage device 411, and then the content of the request is analyzed and its execution is checked 1j'. If there is no error in the request, the request will be acknowledged in the internal status table, and at the same time, the requester will be informed that the request has been accepted. introduce. The internal status table indicates that the same storage information unit is not in normal storage, but is still on the spool. When viewed from outside the device in terms of the system, it is difficult to see the specific location of the storage information unit. That is, in this state, if there is an external read request for the same, #, or H information, the data can be read out in exactly the same way as normal.

The information units on the spool are moved from the spool to the original main storage area after redundancy is removed using the expansion algorithm described in the main text. In this device, there is a process to remove the redundancy mentioned above, and a process to accept and analyze the next request. Do it in parallel. Since the technique of executing W tasks in parallel is a well-known technique, a description thereof will be omitted.

Now, what about Figure 10 in more detail than the processing fee until the memory is completely completed? I will explain using (a) of the figure shows a situation in which the storage request has been accepted, and (b) shows a situation in which the entire storage process has been completed. When viewed from the outside, V'1(a) appears to have completed storage.

The sub storage device 411 has the entire storage area 611 in FIG. 10, which is four sub areas 621, 622, 623,
It's about 24 minutes. These are the catalog for the secondary storage device 410, the catalog of the secondary storage device 411 itself, the spool, and the main storage area. Also, the secondary storage device 410
is also stored in the storage area 610.

Now, it is assumed that the first version of the document Text, 1 and the second version 'l"ext, 2 were stored before the storage request. The former 6
53 is older than the latter, so it is stored in the area 610, and the latter 652 is the latest version at that time, so it is stored in the area 624. If there is a request to store 3, 3rd edition 'll'exe, then the request will be accepted. Immediately after, as shown in Figure 1O (a), 'l'ex
The body 651 of t,3 is in the spool area 623.

Detects the existence of information units in the spool and rewrites the stored contents (to remove redundancy)? Start. The processing result is shown in FIG. 10(b).

Differences (differences) r from the 2nd edition Text, 2 and the 3rd edition Text, 3 are extracted and the area 61 is extracted as an information unit 655.
0 and the original information unit 652 is deleted. Catalog information in catalogs 621 and 622 is rewritten accordingly. Next, the text body 505 (FIG. 9) in the information unit 651 in the spool? It is written in the area 624 as an information unit 654. Catalog 622 will also be rewritten accordingly.

Therefore, the changes 653 and 655, excluding redundancy, are stored in the secondary storage device 410 (optical disk), realizing efficient storage.

Furthermore, the latest version 654, which is frequently accessed, is stored in its original form (n1 access time is short as before), -1゜older version?
When accessing, restore sequentially from the latest version to the older version based on the difference information. Therefore, the access time will be longer even for the latest version. The restoration method is the same as the method used in editors that edit text line by line, and is well known, so the explanation will be omitted.

In order to prevent extremely slow access times for very old versions, this device stores each version (K can be specified as a parameter) in its original form. For example, if I (=3),
Text, 3, Text, 6, . . . are stored in the optical disk file without removing redundancy.

This eliminates the need to create a long chain of restoration processes.

As described above, according to this embodiment, documents with many heavy files with different versions? By automatically extracting different parts, the document is stored in a form with redundancy removed, and as a result, it is possible to store a larger amount of documents in the same storage capacity than before.

In this embodiment, the secondary storage #410 is an optical disk that cannot be replaced, but a magnetic disk may be used instead of an optical disk, and the secondary storage #410 may be integrated with the secondary storage 411. It may also be a magnetic disk drive.

Furthermore, it goes without saying that this storage method can be applied as is to other storage devices such as magnetic tape.

Furthermore, the document may be in Japanese or European language. The only difference is the length of the character code (the former is 2 bytes, the latter is 1 byte) and the character code used for division when performing extended pattern matching. Whether the document is in Japanese or European is recorded in the file attributes of the third record 503 in FIG. division 7
In addition to blank spaces and line breaks, symbols for doing this may also be ".", ",", or a set of these in Japanese.

Also, in this example, is there a difference between the two texts? Everything was requested automatically, but supplementary information from the source of the memory request, for example, an editor in a certain building? You can take it as a hint. For example, if you have a long document, how about dividing it into blocks and flagging blocks that have changed? I can't even think of standing up. Such extensions are also included in the present invention.

Furthermore, a document does not necessarily have a character code of 9, but may also contain a mixture of figures and images. Furthermore, handwriting data such as comments input from an online tablet may also be included.

However, in these cases, different types of data are grouped into the same type of data and put into blocks called data envelopes. In such a case, should the method of the present invention be used for each block? Can be applied.

Also, in this case, was there a change for each delta envelope? It is also possible to identify and remove redundancy as a data envelope r unit.

For example, if you add comments to the first version of a document from an online tablet, you can create a second version of the document by remembering only the comments and the pointer for the main body.
All such extensions are also included in the present invention.

〔Effect of the invention〕

According to the method of the present invention, overlapping portions and different portions are automatically extracted from duplicate storage information units, and redundancy is removed before storage. Yoshi is also able to memorize a large amount of news.

Especially documents? In many cases, a large number of different versions differ from each other by only a few percent. Assuming that there are 5 versions of a document with a length of 100 that differs by 10%, the conventional storage method would store 500 copies, and the inventive method would store 140 copies (as K-5).
→-α's self 1. It's only a small amount, about 3 times as much? can do.

This effect is particularly great in recording devices that cannot be rewritten, such as optical discs.

As a side effect, in the past, due to the limitations of the memory world, the memorization of old versions, which is the process of document creation, was not done because there were many N-folds, but by adopting this method, all processes can be preserved. You can leave it there. Although it is difficult to measure this effect quantitatively, it does affect the quality of work carried out as a document management medium.
? It can be improved significantly.

[Brief explanation of drawings]

Is Figure 1 the method of the present invention? Figure 2 (1) is a diagram explaining the basic principle of the present invention, and Figure 2 (2) i3) is a diagram of the system of the storage device to which it is applied.
The figures shown in Figures 3 to 6 each automatically match/difference text? An explanatory diagram of the extraction method, Figure 7 shows the four methods? Flowchart of the algorithm to be realized, 'iR8 diagram is a diagram showing the structure of the extended algorithm complete explanatory data, No. 10
The figure is a diagram showing the relationship between the 11th device's description and the leaning castle. Buttocks 3 Figure, S2 Figure 4 Child 7 Mouth (3) Figure 7 (4) Red Figure 7 (S) Figure 7 (Nitsu)

Claims (1)

[Claims] A difference between a first information unit to be stored and a second information unit that has already been stored is extracted, and a third information unit is used instead of the first information unit. An information storage method characterized by the ability to store information as