Subject: string arrays

From: pence at heawk1.gsfc.nasa.gov ( William Pence)
Date: Fri, 19 Jun 1992 20:13:10 GMT

Convention for Character String Arrays in FITS Binary tables.

      In the proposed FITS binary table format (Cotton and Tody, 20 Sept
1991) one can define a table column as an array of single characters
(e.g., TFORMn = '20A' indicates that the column is 20 characters wide),
but there is no strictly defined convention to indicate that a column
contains an array of strings.  To take the same example, suppose the
20-character field is composed of 5 4-character length strings
(e.g.,'BearDuckBirdFishWorm').  The question then is what convention
should be used within FITS for storing the information about the length
of strings so that FITS readers and writers will know how to interpret
the sequence of characters in a table column.   One could use the
convention proposed in Appendix A and add a keyword to the header of
the form:

TDIMn = '(4,5)'

however I don't like this for a variety of reasons.  Instead, I propose
that the following convention, which is completely consistent with the
proposed binary table standard, be appended to the binary table
definition document.  Any comments or suggestions are welcome.

-Bill Pence, GSFC/HEASARC                      pence at tetra.gsfc.nasa.gov
                                               LHEAVX::PENCE

--------------------------------------------------------------------------
                        Appendix C

            "Character String Array" Convention

The binary table format allows any field of a table to be an array, but
there is no simple convention for defining arrays of fixed-length
strings within an ASCII character field.  Since the use of fixed-length
strings is arguably the simplest and most convenient way to represent
arrays of strings within FITS (readers and writers can then directly
compute the offset to any substring within the field) this merits
having a special convention for this purpose.  This convention uses the
optional characters which are allowed to follow the datatype code
character in the TFORMn keyword value (described in section 3.9 of the
definition document) to specify the length of the character stings
within the field.  The value of the TFORM keyword then has the form
'rAw' where r is an integer specifying the total number of characters
in the table field and w is an optional integer specifying the width
of the fixed-length character strings within the field.

FITS readers and writers which recognize this convention can then
efficiently access individual strings within the field;  other FITS
readers and writers can simply ignore the optional w characters in the
TFORMn keyword and treat the field as a single one-dimensional array of
characters (unless some other convention for defining string lengths is
recognized).

It is recommended that the value of r should be an integer multiple of
w, however, if this is not the case then any remaining characters after
the last string in the field should be considered as undefined.  For
example if TFORMn = '23A4' then the field should be interpreted as
containing 5 strings each 4 characters in length, followed by 3
undefined characters.  If the value of w is greater than r, or if w is
not an integer, then it does not conform to this convention and should
be ignored (or interpreted under some other convention).

The following examples illustrate the use of this convention:

      TFORMn                  Interpretation
      ------               --------------
       '20A'                 a single string 20 characters in length
       '20A4'                5 strings each 4 characters in length
       '23A4'                5 strings each 4 characters in length followed
                             by 3 undefined characters
       '20A100'              a single string 20 characters in length
                              (w is greater than r so should be ignored)
       '20A/000'             a single string of 20 characters in length
                              (the unrecognized character following the
                              datatype code character should be ignored)

This convention is optional and will not preclude other conventions.  This
convention is not part of the proposed binary table definition.

---

From: tody at noao.edu (Doug Tody)
Date: 21 Jun 92 22:09:16 GMT

>From article <pence.708984790 at heawk1>, by pence at heawk1.gsfc.nasa.gov ( William Pence):
> 
> ...however I don't like this for a variety of reasons.  Instead, I propose
> arrays of strings within FITS...

Bill and I discussed the general problem of arrays of strings in a
get-together following the WGAS meeting at the Columbus AAS.  My conclusion
after this discussion was that the fixed length substring approach Bill
proposes as a convention above is too restrictive to be put forward as the
recommended way to solve this problem.

To see why this might be so we can examine two alternative approaches to the
problem of representing arrays of strings.

1) The fixed length substring approach.  In this case we have something
like the following for a "72A12" string array.

    "red         green       blue        yellow      turquoise   aquamarine"

2) The delimited string approach.  In this case the declaration might be
something like "43A/040" and the stored data might look as follows.

    "red green blue yellow turquoise aquamarine"

In both cases the array-of-strings is stored as a simple NUL terminated
binary tables character array, and the convention used is compatible with
the binary table definition.

The fixed length substring approach is convenient for random access but is
wasteful of space and imposes a rather severe limit on the length of each
substring.  The delimited substring approach can only be accessed
sequentially, but is space efficient and removes the restriction on the
length of a substring.  If the delimiter character is parameterized as in
the example declaration, common delimiters such as blank, comma, newline, or
maybe even EOS (NUL) may be used, with obvious applications to various types
of text data.  There is a wealth of experience in C demonstrating how to
access delimited strings efficiently, so I don't consider the sequential
access limitation serious.

There is a third approach which is a variant of the fixed length substring
approach, but using TDIM to define the length of each substring.  This is
equivalent to what Bill suggests except for the declaration syntax.

In my opinion the second approach suggested above is the better one, since
it is space efficient (preferred for an archival storage format like FITS)
and since it is much more general in the range of string data which can be
stored.  The main point I want to make though, is that the convention Bill
suggests is by no means the only one, and is not necessarily even the best
one.  If we have to add a convention for representing arrays of strings,
one which permits *either* fixed length or delimited substrings would be
preferred.

	Doug Tody
-- 
Doug Tody, National Optical Astronomy Observatories, Tucson AZ, 602-325-9217
UUCP: {arizona,decvax,ncar}!noao!tody  or  uunet!noao.edu!tody 
Internet: tody at noao.edu             SPAN/HEPNET: NOAO::TODY (NOAO=5355)

---

From: leb at Hypatia.gsfc.nasa.gov (Lee E. Brotzman)
Date: Mon, 22 Jun 1992 20:57:46 GMT

>    "red green blue yellow turquoise aquamarine"

I really don't see how the second approach is going to save much space because
of the restriction that all rows in binary tables must be of the same length.  
Suppose one row has the colors listed as above but the same field in the 
following row is 

     "aquamarine turquoise yellow tangerine chartreuse avacado"

The field's TFORM must now be "58A/040". In general, the maximum possible width
for the field must be reserved and zero-filled when the string is shorter than
the maximum.  The only alternative is to use the variable array feature, which
I think is outside of the discussion at hand.

Personally, if the fixed-field way is chosen (I'm currently undecided about
*which* is best), rather than having the TFORM for example (1) above be
"72A12", I would much prefer "6A12".  The interpretation being that "A12"
denotes a character object 12 bytes in length and there are an array of 6 of
them.  I like this much better than the interpretation of 72 objects of type 
'A' of which 12 are "subgrouped", as it were.  It's cleaner to have the number
following the 'A' be a modifier of just the data type, not of the data type
and array length.

In fact the same notational conventions can be applied across the board to 
the other data types cleanly, e.g. "16I5" would be interpreted as an array of
16 elements where each element is a 5-tuple of 16-bit integers.  This would
give FITS at least marginal object orientation.  Nothing as useful as ASN.1 or
ODL, but you have to start somewhere.

-- Lee
--
-- Lee E. Brotzman                    Internet:  leb at hypatia.gsfc.nasa.gov
-- Hughes STX                         DECNET:    NDADSA::BROTZMAN
-- National Space Science Data Center BITNET:    ZMLEB at SCFMVS
-- NASA Goddard Space Flight Center

---

From: leb at Hypatia.gsfc.nasa.gov (Lee E. Brotzman)
Date: 27 Jun 92 02:13:06 GMT

>ODL, but you have to start somewhere.
 
  I'm a little surprised that my previous message has yet to elicit a response.
The notational convention I mentioned is sufficiently powerful that at least I
expected some opposition to it.  Therefore I'll press my case....

   As a standing member of the NASA technical committee on the NOST FITS
standard, I will reserve my vote on the addition of the Binary Tables
extension until the matter of this more powerful notation convention is
resolved.  

   I am not hard-headed about it, I just would like to see some debate.  What
are the implications for FITS readers that may have to deal with structures
that are of this form?  What possible applications can benefit from this
notation?  From the top of my head, some data objects that are natural for this
are coordinates -- they are RA/Dec, Latitude/Longitude, Altitude/Alzimuth
pairs.  A structure that defines an area could be an array of these
two-dimensional values, e.g. '120E2' could describe a set of 120 points in
2-dimensional space that encloses a constellation or some other irregular area
of the sky.  It can also describe 120 points in a flux/wavelength spectrum.
The uses seem endless.

   Let's talk about it.

---

From: tody at noao.edu (Doug Tody)
Date: Sat, 27 Jun 1992 05:13:30 GMT

>From article <leb.709611186 at Hypatia>, by leb at Hypatia.gsfc.nasa.gov (Lee E. Brotzman):

Ok Lee - as you probably expected, I at least don't like your suggestion.
What you suggest seems like just a gee whiz feature to me.  There is no case
for it, we don't know what it might be useful for.  One doesn't just stick
features in a specification (especially a standard) because they *might* be
useful.  We already have a draft binary tables specification out there which
took years to get to where it is, and a pretty good case has to be made to
make such a significant change.

The suggestion proposed by Bill Pence, which I repeated in my earlier
posting, e.g., "72A12", has the advantage of being compatible with the
current binary table specification.  The basic binary tables specification
supports only 1 dimensional arrays; in the example 72 is the array length.
Your suggestion would be a major change, but all it does is add a restricted
2 dimensional array facility.  If we are going to go to the trouble to
support arrays of greater than 1 dimension then we should do something
more general.  The TDIM convention is better, at least it supports arrays of
arbitrary dimension.

The basic binary tables field type specification, as in "72A", purposely
states that characters may follow the type character, and that the meaning
of these characters is not defined by the basic binary tables
specification.  This was done to allow experimentation with things like
array specification in the type specifier.  For example, it is possible that
some sort of syntax can be defined using the type specifier which would
eventually prove better than TDIM.  In the meantime naive software can treat
the stored object as a simple one-dimensional array, or "blob" - this is
desirable in any case, as many table access operations do not require
knowledge of the contents of a "blob" or array.  Bill's original suggestion
is consistent with this approach.  Your's isn't, and would make it more
difficult to reserve space in the type specifier to experiment with layered
conventions.

I already don't like fixed size arrays for character data; as I have argued
previously, even in the case of strings there may be better ways to represent
the data.  Delimited strings are much more flexible in the range of data
which can be represented (e.g. a sequence of lines of text, like this
message), and are simple and efficient to use for simple sequences of
strings as well ("red green blue" etc.).  You don't have to buy this
argument, the point is that since it can be debated so easily, we should not
lock any one approach into the standard.  You are suggesting we not only
standarize on an array of fixed length strings for character string storage,
but define the same awkward construct for all data types as well.

One dimensional arrays are fundamentally different than multidimensional
arrays, because any arbitrary data object can be stored in a one dimensional
array, and the NxM-etc. multidimensional array is only one such object.  An
array of strings is another, as is a sequence of delimited strings, or a
data structure encoded as a byte stream.  There are many types of objects
which could be stored in an array.  The one dimensional array, or "blob", is
a general method for storing objects in a database.  It can be treated in a
well defined fashion by generic programs without need to understand the
nature of the object stored in the array.

One dimensional arrays (including variable length arrays in Appendix B) are
defined by the standard because they are fundamentally important and
reasonably well understood.  As soon as we start looking at more complex
objects we get into discussions like this one - that is why the current
binary tables specification stops where it does.  Experimentation with
layered conventions is required to learn how to store more complex objects.

Doug Tody

---

From: warnock at Hypatia.gsfc.nasa.gov (Archie Warnock)
Date: Sat, 27 Jun 1992 18:18:58 GMT

>expected some opposition to it.  Therefore I'll press my case....

Maybe it was so intuitively obvious that no one thought it wasn't part
of the proposal.

>   Let's talk about it.

Other than reservations about it being too "Fortran-like", it's an
excellent addition.  I'm in favor of it.  I'm not even biased just
because you're across the hall from me...

--
----------------------------------------------------------------------------
-- Archie Warnock                   Internet:  warnock at hypatia.gsfc.nasa.gov
-- Hughes STX                       "Unix --- JCL For The 90s"
-- NASA/GSFC

---

From: thompson at stars.gsfc.nasa.gov (William Thompson, code 682.1, x2040)
Date: 27 Jun 92 23:51:00 GMT

In article <leb.709611186 at Hypatia>, leb at Hypatia.gsfc.nasa.gov (Lee E. Brotzman) writes...
>of the sky.  It can also describe 120 points in a flux/wavelength spectrum.

All right.  First of all, let's consider 72A12 vs 6A12 for a series of six
character strings of 12 characters each.  Although I agree that the latter is
more elegant, the former preserves the property that the first number and the
character code gives the number of bytes taken up by that particular column.
One could still theoretically read the file even if one's reader did not
understand the part following the datatype code character.

As for the rest, I believe that the proposal is so restrictive as to be almost
useless.  The effect of this proposal is to allow for two-dimensional arrays,
although you describe it somewhat differently.  I believe that N-dimension
capabilities are needed, such as the TDIM or Green Bank conventions provide
for.  (Some astronomical data I've worked with have has as much as six
dimensions.)

Character string arrays are something of an exception, since the number of
characters in each string is a property quite distinct from the dimensions that
the characters may be organized into.

It has been quite correctly pointed out that there are at least two ways of
delimiting character strings, by a preset number, or by a delimiter character.
One also has to consider both fixed and variable length arrays.

At first I was receptive to the 'rAw' proposal.  However, I now feel that it
would be a mistake to expect to be able to store this information in the TFORM
keyword, encompassing all reasonable possibilities.  I believe that the best
approach is to leave the current binary table proposal untouched, and to work
on enhancing its capabilities through the addition of keywords such as TDIM.
For instance:

	TCLENnnn	Character string length for column "nnn"
	TCDELnnn	Character string delimiter (byte value) for column
			"nnn" 

(The above are intended more as examples then as serious proposals, although
they could be.)

On a related issue, an earlier post used the notation "\012" to denote an octal
value.  While this is standard C and UNIX usage, I believe that its use in FITS
files would be new and unprecedented.  I don't necessary say that it's a bad
thing.  A standard for expressing values in octal (or even hexadecimal)
notation would be valuable.  It would have to be carefully looked at, though.

Bill Thompson

---

From: ahenden at magnus.acs.ohio-state.edu (Arne A Henden)
Date: Mon, 29 Jun 1992 13:21:39 GMT

>expected some opposition to it.  Therefore I'll press my case....
I agree with Doug in this case.  TDIM for fixed-size items plus the
variable length array extension handles all the cases you've mentioned.
The major benefit of the simplistic element count for TFORM is that
a simpler file reader can be written that ignores columns.
  If you are really concerned about a Fortran-like interface, why
not something like 72A(6A12), which fits the proposed format.

---

From: pence at heawk1.gsfc.nasa.gov ( William Pence)
Date: Mon, 29 Jun 1992 19:28:25 GMT

>following the 'A' be a modifier of just the data type, not of the data type

I had originally proposed using exactly this convention (e.g., "6A12")
last year in my comments about the bintable format and have  even
implemented it in the current FITSIO package.  However, since it
appears that this suggestion is about to be shot down (the Europeans
apparently favor sticking with the original wording of the bintable
format) I proposed the new way of representing fixed length strings in
the tform keyword (e.g., "72A12").  Since this new proposal is entirely
consistent with the proposed binary table format, people cannot object
to it for that reason (although they may have other objections) and it
should be easier to gain acceptance for the proposal.

As the implementor of FITSIO, I really don't care which form ("6A12" or
"72A12") is chosen, since they are equally easy to implement.  All I ask
is that something like this be adopted so that we don't have to go 
through some other clumsy procedure (like looking for TDIMn keywords) just
to support a simple one dimensional array of strings.   The TFORMn keyword
is all that is needed to support one dimensional arrays of every other
possible datatype (logical, bit, byte, short integer, long integer, reals,
double precision, complex, double complex) so why can't one dimension
arrays of stings be supported as well??  The answer is that they can be
supported by using the simple syntax that I have proposed.

As Doug Tody wrote:
  "One dimensional arrays are fundamentally different than multidimensional
  arrays, because any arbitrary data object can be stored in a one dimensional
  array... [stuff deleted]... The one dimensional array, or "blob", is
  a general method for storing objects in a database.  It can be treated in a
  well defined fashion by generic programs without need to understand the
  nature of the object stored in the array."

I agree with this and am simply trying to find a  way within the
proposed bintable format to  support one dimensional arrays of
strings.   Note that I also have no objections to using the TDIMn
keyword to express the higher dimensionality of arrays of ANY
datatype.  I just object to requiring that the STRING datatype be the
ONLY  datatype which requires the use of the TDIM keyword to express
one-dimensional arrays.  This objection is based on a very practical
consideration:  the FITSIO package only deals with binary table columns
as one-dimensional arrays.  Thus, except for string arrays, the FITSIO
code does not have to worry about reading or writing  TDIM keywords;
It is left up to the higher level calling program to worry about any
higher dimensionality, if it is appropriate.

Doug Tody has objected to my proposal on the grounds that there may be
other ways to express arrays of strings rather than just as fixed
length arrays (e.g., null terminated strings).  To this I would reply
that my proposal in no way excludes alternative ways of encoding arrays
of strings (this is explicitly stated at the end of my proposal).  All
I am proposing is that IF someone wants to write an array of fixed
length strings into a column, then he/she MAY use the proposed 'rAw'
TFORM format to express this.   Just as an example of alternative ways
of writting strings, one could write TFORMn = '72A/000' to signify a 72
character field containing strings terminated by nulls (octal 000).  I
do not advocate using delimited strings withing FITS files because I
think it could be a nightmare to implement, but still, my proposal does
not preclude such conventions from being used.

As a final comment, I don't think that using delimited strings is a
very good idea in FITS files.  First, one must allocate a fixed width
in the binary table column anyway, which seriously restricts the
usefulness of varable length strings (delimited strings) within the
field.  The only advantage to using delimited strings is that one can
use some of the unused space from one string array element and use it
for a longer element somewhere else in the array.  But practically
speaking I think one would end up wasting more space in the table due
to having to have delimiter characters between each string element,
than if one just had fixed length strings in the first place.

The really major disadvantage that I see to using delimited strings in
FITS files is that one has no idea how many elements of
the string array are in a given row of an ASCII column making it
impossible to directly offset to any particular element within the
string array (unlike every other datatype which has a fixed element
size).  For example, if someone calls one of my FITSIO subroutines to
write an array of 20 strings into a TFORM='36A' column using delimited
strings then FITSIO won't know how many strings should be packed into
each row of the table.  Should it try to force all 20 stings into one
36 character row?  Or at the other extreme, should FITSIO write one
string into 20 consecutive rows of the table??   If, on the other hand
we use fixed length strings then the meaning is very clear.  If for
example TFORM = '36A18'  then FITSIO would know that the 20 strings
should be written as 2 18-character strings on 10 consecutive lines of
the table.

>ODL, but you have to start somewhere.

I agree with Doug here in that generalizing this TFORM convention to
other datatypes offers too little new functionality to be of much general
use.  This basically  is just a way to specify 2-dimensional arrays,
but I think is would be better to have a single general way to specify
arrays of any number of dimensions (e.g., the TDIMn  keyword).
(Some might argue that following this same logic, one should consider
an arrays of fixed length strings as a 2 dimensional array of
characters, and hence one should stick with the TDIM convention for
specifying the string length.  I don't buy this arguement however
because I regard a string as a fundamental datatype in its own right,
quite different from an array of characters.  In the real world people
want to be able to deal with a string as a single entity.  The fact
that the string can be broken down into an array of characters is no
more relevant than the fact that an integer can be broken down into an
array of bits.)

-Bill Pence
pence at tetra.gsfc.nasa.gov
LHEAVX::PENCE

---

From: thompson at stars.gsfc.nasa.gov (William Thompson, code 682.1, x2040)
Date: Mon, 29 Jun 1992 21:34:00 GMT

In article <pence.709846105 at heawk1>, pence at heawk1.gsfc.nasa.gov ( William
Pence) writes...

	(message deleted to save space)

I don't really see anything wrong with William Pence's 'rAw' proposal, as such.
I agree that the length of a string is fundamentally different than the
dimension of an array.  The trouble starts when trying to extend this idea to
other ways of storing string arrays.  One can either store fixed-length
strings, or delimited strings.  It's been suggested that the latter case be
identified by "rA/ooo" where "ooo" is the octal representation of the delimiter
character.  However, what would you do about character strings stored as
variable length arrays?

I also agree that TDIMn, while a valuable resource, should not be necessary if
all one wants to do is specify where one string ends, and the next begins.

That's why I suggested that the separate keyword TCLENn, or something like it,
be used to specify the number of characters in each string.  The beauty of this
approach is that it works for both fixed and variable length arrays.
Alternatively, one could use the keyword TCDELn, which takes an integer value
between 0 and 255, to represent the character that delimits each string.

The idea of having "A" followed by a number whose meaning changes if it is
given in decimal or octal notation bothers me.  I agree that it can be properly
interpreted by the computer, but I disagree with it on philosophical grounds.
If we use it this way now, we severely restict the use of octal and hexadecimal
constants in the future.

Character strings are fundamentally different from other data types, and
there's probably no completely satisfying way around that fact.

Bill Thompson

P.S.  A separate issue comes up when one does want to use the TDIM keyword, or
      some other way of specifying dimensions, together with either Pence's
      'rAw' or my TCLEN proposal.  Does one include the string length in both
      TDIM and TFORM, which would be consistent with the way that Appendix A of
      the Binary Tables Extension proposal currently reads, or would one only
      put the regular dimensions in TDIM, which would be more consistent with
      allowing both fixed character length and character delimiter
      possibilities.